Problem Statement

A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers.

Given a string s, return true if it is a palindrome, or false otherwise.

Additional information

• 1 <= s.length <= 2 * 10^5
• The string consists of printable ASCII characters.
• You must ignore spaces, symbols, and punctuation.

Example 1:

Input: s = "A man, a plan, a canal: Panama"

Output: true

Example 2:

Input: s = "race a car"

Output: false

Example 3:

Input: s = " "

Output: true

Reverse String (Naive)

Intuition
The simplest conceptual way to check for a palindrome is to "clean" the string first. We can create a new string containing only the lowercase alphanumeric characters from the original. Once we have this clean string, we simply compare it to its reverse. If they are identical, it is a palindrome.

Algorithm

1. Initialize an empty string (or list) new_str.
2. Iterate through the original string s.
3. If a character is alphanumeric (letter or number), convert it to lowercase and append it to new_str.
4. Create a reversed version of new_str.
5. Compare new_str with the reversed version. Return True if they match, False otherwise.

def is_palindrome(s: str) -> bool:
    new_str = ""
    for c in s:
        if c.isalnum():
            new_str += c.lower()
    return new_str == new_str[::-1]

Time & Space Complexity

• Time complexity: O(n)

• Reason: We iterate through the string once to filter it, and then reverse it (which also takes linear time).

• Space complexity: O(n)

• Reason: We create a new string new_str that can be as large as the original string.

Two Pointers (Optimal)

Intuition
We can solve this without using extra space by using two pointers. One pointer starts at the beginning of the string, and the other starts at the end. We move them towards each other, skipping any non-alphanumeric characters. If the characters at the valid pointers don't match, it's not a palindrome. This avoids creating a new string entirely.

Algorithm

1. Initialize two pointers, l (left) at 0 and r (right) at len(s) - 1.
2. While l < r:

• Move l forward if s[l] is not alphanumeric.
• Move r backward if s[r] is not alphanumeric.
• If both pointers are on valid characters, compare s[l].lower() and s[r].lower().
• If they are different, return False.
• Otherwise, move both pointers inward (l += 1, r -= 1).

3. If the loop finishes without mismatches, return True.

def is_palindrome(s: str) -> bool:
    l, r = 0, len(s) - 1

    while l < r:
        if not s[l].isalnum():
            l += 1
        elif not s[r].isalnum():
            r -= 1
        elif s[l].lower() != s[r].lower():
            return False
        else:
            l += 1
            r -= 1
    return True

Time & Space Complexity

• Time complexity: O(n)

• Reason: We traverse the string at most once using the two pointers.

• Space complexity: O(1)

• Reason: We only use two integer variables (l and r) and do not allocate new memory for the string.