Valid Palindrome
Valid Palindrome: decide whether a string reads the same forwards and backwards, considering only alphanumeric characters and ignoring case.
- 1 <= s.length <= 2 * 10⁵
- s consists only of printable ASCII characters.
Intuition
Valid palindrome checks whether a string reads the same forwards and backwards, considering only alphanumeric characters and ignoring case.
The filtering rules are where the problem lives — the palindrome check itself is trivial.
The straightforward approach builds a cleaned string, keeping only alphanumeric characters in lowercase, then compares it with its reverse. Correct, readable, and O(n) space.
The two-pointer version avoids that allocation:
- Converge from both ends, skipping non-alphanumeric characters on each side, and compare the characters that remain.
Each pointer advances past punctuation and spaces independently, so the two need not move in step. That independence is what makes the skipping loops necessary rather than a single conditional.
Those inner skip loops must also check the pointers have not crossed. A string of only punctuation would otherwise run a pointer off the end — and such a string is a valid palindrome, since it contains no characters to compare.
The empty string is a palindrome for the same reason, and the loop condition handles it by never running.
Case folding must apply to both characters before comparison. Lowercasing only one side compares mismatched cases and rejects valid palindromes.
Digits count as alphanumeric and participate in the comparison — "0P" is not a palindrome, since 0 and P differ.
The two-pointer version gives O(n) time and O(1) space, against O(n) for the cleaned-string approach. That space difference is the reason to prefer it.
Two pointers converging, with each side independently skipping non-alphanumeric characters. The continue after each skip is what keeps the logic flat — re-entering the loop re-tests both guards rather than nesting conditions.
Approach
Before reading on: price up what the direct approach costs here, then ask what makes it safe to discard one end without checking it against everything. Aim for O(n) time and O(1) space.
Identify what to compare
Only alphanumeric characters count, and case is ignored. The palindrome test itself is trivial — the filtering rules are the problem.
Converge from both ends
Place one pointer at each end and move inward, comparing the characters that survive filtering.
Skip non-alphanumeric independently
Each pointer advances past punctuation on its own side. The two do not move in step, which is why separate skip loops are needed.
Guard the skip loops
Check the pointers have not crossed while skipping. A string of only punctuation would otherwise run off the end — and it is a valid palindrome.
Fold case on both sides
Lowercase both characters before comparing. Folding only one side compares mismatched cases and rejects valid palindromes.
Include digits
Digits are alphanumeric and participate fully — "0P" is not a palindrome, since the two characters differ.
Cost of the approach
One converging pass gives O(n) time and O(1) space, against O(n) space for building a cleaned string.
Solution & live demo
Common pitfalls
Skipping only one side per iteration
if not s[l].isalnum(): l += 1 if not s[r].isalnum(): r -= 1 if s[l].lower() != s[r].lower(): return False
if not s[l].isalnum():
l += 1
continueWithout the continue, the comparison runs on a character that was just skipped past but not re-validated — a run of two punctuation marks leaves one still in place. Restarting the loop re-checks both guards.
Forgetting to normalise case
if s[l] != s[r]:
if s[l].lower() != s[r].lower():
The problem ignores case, so 'A' and 'a' must compare equal. Raw character comparison rejects most real-world palindrome phrases.
Building a cleaned copy first
t = ''.join(c.lower() for c in s if c.isalnum()) return t == t[::-1]
l, r = 0, len(s) - 1
Correct and readable, but allocates two extra strings. The two-pointer scan answers in O(1) space, which is the version the follow-up asks for.
Edge cases
The skip loops consume everything, the pointers cross without a single comparison, and the function returns True — the empty sequence is trivially a palindrome.
Digits are alphanumeric so they participate; lowercasing '0' is a no-op and 'P' becomes 'p', so '0' vs 'p' correctly fails.
The pointers land on the same index and the loop exits, so the middle character is never compared to anything — which is correct, it mirrors itself.
The l < r guard inside each skip loop stops the pointers from running past each other, and the answer is True.