Valid Palindrome

A phrase is a palindrome if, after lowercasing and removing every non-alphanumeric character, it reads the same forward and backward. Return whether s is a palindrome.

Examples

Input:  "A man, a plan, a canal: Panama"   -> True
Input:  "race a car"                        -> False
Input:  " "                                 -> True   # empty after cleaning

Constraints

• 1 <= len(s) <= 2 * 10^5, printable ASCII.

Approach — two pointers skipping junk

You could build a cleaned string and compare it to its reverse — but that's O(n) extra space. The O(1)-space approach walks a pointer in from each end, skipping any character that isn't alphanumeric, and compares the two valid characters (case-folded).

Solution

def is_palindrome(s: str) -> bool:
    left, right = 0, len(s) - 1
    while left < right:
        while left < right and not s[left].isalnum():
            left += 1
        while left < right and not s[right].isalnum():
            right -= 1
        if s[left].lower() != s[right].lower():
            return False
        left += 1
        right -= 1
    return True

Explanation

• The inner while loops skip punctuation and spaces so the pointers land on real characters before comparing.
• left < right guards inside the skip loops too, so we never run the pointers past each other on a string of all-punctuation.
• .lower() makes the comparison case-insensitive; .isalnum() handles letters and digits (e.g. "0P" is not a palindrome, "aba" is).

Complexity

• Time: O(n) — each pointer advances monotonically; total moves ≤ n.
• Space: O(1) — no cleaned copy.

Interview tips

The cleaner-but-heavier one-liner t = [c.lower() for c in s if c.isalnum()]; return t == t[::-1] is fine to mention — then note the two-pointer version saves the O(n) buffer, which is what the interviewer usually wants.