Lesson 11 — Two Pointers on Strings

~20 minutes · Day 8 · two pointers · Python

Interviewers like Valid Palindrome because it looks like a string cleanup problem, but the real test is whether you can keep two positions honest while ignoring noise. You are not trying to memorize a trick. You are learning a small loop shape that appears whenever the two ends of a string have to agree.

The invariant

Walk one pointer in from each end, skipping what doesn't count, comparing as you go.

That is the whole move. The left pointer starts at the first character, the right pointer starts at the last character, and both move inward. Spaces, punctuation, and symbols do not count for this problem, so the pointers skip them. When both pointers land on letters or digits, compare them in the same case.

The pointers ignore punctuation and spaces, then compare the next real characters.

Valid Palindrome: the copy way first (O(n) time, O(n) space)

The problem says to ignore non-alphanumeric characters and compare case-insensitively. Python gives you str.isalnum() for the “does this count?” question and str.lower() for case normalization.

The beginner solution is to build the cleaned string, reverse it, and compare:

def is_palindrome(s):
    cleaned = []
    for ch in s:
        if ch.isalnum():                 # keep only letters and digits
            cleaned.append(ch.lower())   # compare in one case
    cleaned = ''.join(cleaned)
    return cleaned == cleaned[::-1]      # compare with the reverse

This is clear, and it works. It is O(n) time and O(n) space because the cleaned copy grows with the input. The interview upgrade is to avoid building that copy at all.

Valid Palindrome: the two-pointer way (O(n) time, O(1) space)

Keep the original string in place. Move left until it points at a character that counts. Move right until it points at a character that counts. Then compare.

def is_palindrome(s):
    left, right = 0, len(s) - 1
    while left < right:
        while left < right and not s[left].isalnum():
            left += 1                    # skip left-side noise
        while left < right and not s[right].isalnum():
            right -= 1                   # skip right-side noise
        if s[left].lower() != s[right].lower():
            return False                 # one mismatch breaks it
        left += 1
        right -= 1
    return True

The reason this stays O(n): neither pointer ever turns around. Every character is skipped, compared, or passed once. The reason it stays O(1) space: the loop carries only two indices.

Because both pointers only move inward, the scan is linear.

Transfer: same scan, new costume

Mini-problem: return whether "No 'x' in Nixon" is a palindrome if spaces and punctuation do not count. Before opening the reveal, predict the first two comparisons the pointers should make.

What the trade buys you

The time stays linear either way. The win is that the pointer version does not allocate a cleaned string or its reverse.

Practice — answer before you scroll past

while left < right:
    while left < right and not s[left].isalnum():
        left += 1
    if s[left].lower() != s[right].lower():
        return False
    left += 1
    right -= 1

Your move (tonight)

Solve Valid Palindrome in your Notion tracker using the cycle: predict → attempt → compare → encode.

1. Predict: say the invariant out loud and name the brute force copy approach.
2. Attempt: code the two-pointer loop without watching a solution first.
3. Compare: check your loop against the source below only after the attempt.
4. Encode: write the invariant in your own words in the Notes column.

Stuck or curious? Ask your teacher (the agent) — that's what it's for.