Valid Palindrome

Signal

Checking a string (or array) against its own mirror image, with no auxiliary data structure needed — that's converging pointers from both ends. The trigger phrase: "reads the same forwards and backwards."

Approach

Set one pointer at the start and one at the end. Skip forward past any non-alphanumeric character on the left, skip backward past any on the right, then compare the two characters (case-insensitive). If they ever differ, it's not a palindrome. Move both pointers inward and repeat until they meet.

Skeleton

left, right = 0, len(s) - 1
while left < right:
    while left < right and not alnum(s[left]): left += 1
    while left < right and not alnum(s[right]): right -= 1
    if lower(s[left]) != lower(s[right]): return False
    left += 1; right -= 1
return True

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

Complexity

O(n) time — each pointer crosses the string at most once. O(1) space — no copy of the cleaned string is built.

Pitfalls

• Building a cleaned copy first (''.join(c for c in s if c.isalnum())) works but costs O(n) extra space; the two-pointer version does the filtering in-place as it walks.
• Forgetting the left < right guard inside the inner skip-loops lets both pointers walk off the same end when the string is all punctuation.
• Comparing case-sensitively — 'A' != 'a' will wrongly reject valid answers.