visual walkthrough
Valid Palindrome
The simplest opposite-ends scan, with character filtering.
The idea
A palindrome reads the same from both ends, so you only ever need to compare the outermost characters, then move inward. Two pointers do that without building a cleaned-up copy.
Characters that aren't letters or digits are simply stepped over when a pointer lands on them.
Complexity
| approach | time | space |
|---|---|---|
| Clean and reverse | O(n) | O(n) |
| Two pointers | O(n) | O(1) |