Valid Palindrome
Converge from both ends, skipping non-alphanumerics.
Two Pointers in Action
Problem
Given a string, decide whether its meaningful characters form a palindrome. Ignore punctuation, spaces, and other non-alphanumeric characters, and treat uppercase and lowercase letters as equivalent. Return true when the normalized sequence reads identically from both directions.
Examples
Input: "A man, a plan, a canal: Panama"
Output: true
Input: "race a car"
Output: false
The Goal
Decide whether s reads the same both ways once you ignore everything but letters and digits, and ignore case.
You could build a cleaned copy and reverse it. Two pointers make the same check in place, skipping what doesn't count as they go.
"A, b" cleans to ab, so it isn't a palindrome.
Compare letters and digits only
Spaces and punctuation don't count, and A equals a.
Key Idea: Converge from Both Ends
A palindrome matches at mirrored positions: first with last, second with second-to-last, and so on.
Put left at the start and right at the end. When either lands on a space or punctuation, it skips past. When both are on letters or digits, compare them, ignoring case. A match moves both in.
In "a!a", the two as match, and the pointers meet on the ! without comparing it.
Move a pointer past anything that isn't a letter or digit.
Commas, spaces and colons.
The Algorithm
A mismatch between two letters or digits ends it, because no skipped character can fix it. A match settles that pair, so both pointers move in.
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, right = left + 1, right - 1
return TrueBoth skip loops check left < right, so neither pointer runs off the end.
| Approach | Time | Extra space | Tradeoff |
|---|---|---|---|
| Clean, reverse, compare | O(n) | O(n) | Simple, but stores a cleaned copy |
| Two pointers | O(n) | O(1) | Skips in place |
Walkthrough
Run it on "A man, a plan, a canal: Panama". The pointers start at 0 and 29.
The first pair is A and a, a match once case is ignored. After that, every space and comma gets skipped. left skips most of them, and right skips the space and the colon before Panama.
The pointers meet on the middle c, which is compared with itself. Every pair matched, so it's a palindrome.
Checkpoint · predict the next step
Step 8 of 22 on the stage: Left is on ' ', not a letter or digit. Skip it: move left right.
left on " " (index 6) · right on "a" (index 25) · pairs matched 4
Pitfalls
- Skip on both sides. Skipping on one side compares a letter with a space.
- Compare lowercase forms, or
Aandalook different. - Don't assume the first and last characters count. For
".,A!", both pointers skip to the oneA, and the answer is true. - An empty string, or one that's all punctuation, is a palindrome.
What has to happen before you compare the current characters?
Complexity
The skip loops sit inside the main loop, but neither pointer ever moves back. Each character is skipped or compared about once, so time is O(n). You keep two indices, so extra space is O(1).
A mismatch returns early. That helps in practice, but not in the worst case.
One inward scan
- Move both pointersInward only.dominantO(n)
- Compare pairsEach character in at most one pair.dominantO(n)
- Extra stateTwo indices, no cleaned copy.O(1)
| n | 10 | 100 | 1,000 | 10,000 |
|---|---|---|---|---|
| O(n) | 10 | 100 | 1K | 10K |
Linear time, with no copy of the string.
In short
Put one pointer at each end. Advance past any non-alphanumeric character, compare the two (case-insensitively), and move inward. If any pair differs it's not a palindrome. This avoids building a cleaned copy of the string.
Common mistake
Forgetting to skip punctuation/spaces on both pointers, or comparing without normalizing case.