Valid Palindrome

Given a string, return true if it is a palindrome after lowercasing and removing all non-alphanumeric characters. Otherwise return false.

A new filtered string works but costs extra memory. A two-pointer scan reads the original string using constant auxiliary space.

Why this is worth learning

Skipping punctuation is a traversal rule, not an instruction to allocate a cleaned string. Compare the next surviving byte at each end; the source string remains unchanged.

Before coding: one-minute experiment

What should the function return for "0P" and for " , "?

Function signature

func IsPalindrome(s string) bool

Inputs / outputs

• s: input string (ASCII letters/digits and punctuation).
• Return: true if the cleaned string is a palindrome.

Example

s = "A man, a plan, a canal: Panama"
Output: true

Cleaned: "amanaplanacanalpanama"

Constraints

• 0 <= len(s) <= 200_000

Core idea (near-solution)

Use two pointers l and r from both ends:

• Move l right until it hits an alphanumeric character.
• Move r left until it hits an alphanumeric character.
• Compare lowercased characters; if they differ, return false.

Invariant: all characters outside [l, r] have already been validated.

Algorithm (step-by-step)

1. Set l = 0, r = len(s)-1.
2. While l < r:
   • Advance l until s[l] is alphanumeric or l >= r.
   • Decrease r until s[r] is alphanumeric or l >= r.
   • If the skips make l >= r, stop: no unmatched pair remains.
   • Compare lowercased s[l] and s[r]; if different, return false.
   • Move l++, r--.
3. Return true.

Correctness sketch

Before each comparison, every retained pair outside [l,r] has matched after ASCII lowercasing. Skipping a non-alphanumeric byte removes nothing from the cleaned sequence because that byte is excluded by definition. The next retained bytes are therefore the outermost unmatched pair. A mismatch disproves the palindrome; a match removes two equal endpoints without changing whether the interior is a palindrome. Each skip or match reduces the remaining interval. With at most one retained byte left, no unmatched pair can fail, so returning true is correct.

Trace (hand walkthrough)

s = " A,b!a " (indices 0..6)
- l=0 is a space: skip to l=1 ('A')
- r=6 is a space: skip to r=5 ('a')
- fold ASCII case: 'A' and 'a' match; move l=2, r=4
- skip comma at 2 and ! at 4: l=r=3 ('b')
- the center needs no partner; return true

This trace reads the source indices directly; it never constructs a cleaned copy.

Pitfalls to avoid

• Forgetting to skip non-alphanumeric characters on both ends.
• Comparing without lowercasing.
• Off-by-one when the string is empty.

Debugging lens

Test digits as well as letters, mixed case, punctuation at both boundaries, and punctuation-only input. A filter that retains letters but drops digits silently changes the problem.

Complexity

• Time: O(n)
• Extra space: O(1)

Implementation notes (Go)

• This statement assumes ASCII letters/digits.
• Implement small helpers isAlphaNum and toLower for bytes.

Contract precision

This is an ASCII alphanumeric comparison. It is not Unicode case folding or grapheme comparison. The Go string is read, not mutated.

Reconstruction checkpoint

What should the function return for "0P" and for " , "?

Return to Two Pointers · Module quiz