Valid Palindrome

Valid Palindrome is the gateway to the two-pointer pattern. It looks like a string problem, but the real lesson is how to walk a sequence from both ends at once — using O(1) extra space.

The slow way first

The obvious idea: build a cleaned-up copy of the string — keep only letters and digits, lowercase them — then reverse it and compare. That works:

clean = [c.lower() for c in s if c.isalnum()]
return clean == clean[::-1]

But it allocates two extra strings/lists of size n. We can do the same check with no extra space by comparing characters in place from both ends.

The idea: two pointers closing in

Put a pointer l at the start and a pointer r at the end. A palindrome means s[l] must equal s[r] for every matching pair as we walk inward. So:

• If s[l] is not alphanumeric, nudge l right and try again.
• If s[r] is not alphanumeric, nudge r left and try again.
• Otherwise both are real characters — compare them lowercased. A mismatch means not a palindrome. A match means step both pointers inward.

When l and r cross without ever finding a mismatch, it is a palindrome.

The key insight: skipping non-alphanumeric characters is just moving one pointer without moving the other. We never copy the string.

Walk through it

Step through the animation. l and r start on the outer "R" and "r", which match. They march inward through "a"/"a" and "c"/"c". Then r lands on a space and a comma — both not alphanumeric — so r slides left twice while l waits. Both pointers meet on "e", match, and cross. No mismatch was ever found, so the answer is True.

Pseudocode

l = 0, r = last index
while l < r:
    if s[l] is not alphanumeric:   move l right
    elif s[r] is not alphanumeric: move r left
    elif lowercase(s[l]) != lowercase(s[r]): return False   # mismatch
    else:                          move l right and r left  # matched pair
return True                        # crossed with no mismatch

The Python solution

def is_palindrome(s):
    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

• l, r = 0, len(s) - 1 start the two pointers at the ends.
• The first two if/elif branches skip non-alphanumeric characters — only one pointer moves.
• s[l].lower() != s[r].lower() is the actual comparison; .lower() makes it case-insensitive.
• The final else runs only when both characters are real and equal, stepping both inward.
• If the loop finishes (pointers crossed) without returning False, the string is a palindrome.

Complexity

Every character is looked at a constant number of times as the pointers sweep toward each other, so it is O(n) time. Because we never build a copy, it is O(1) extra space — the win over the clean-and-reverse approach.

When this pattern shows up

Practice