Valid Palindrome
Check a string reads the same both ways using two pointers that skip non-alphanumeric characters
Problem Statement
A phrase is a palindrome if, after converting all uppercase letters to lowercase and removing every non-alphanumeric character, it reads the same forwards and backwards.
Given a string s, return true if it is a palindrome.
Input: "A man, a plan, a canal: Panama"
Output: true
Why: cleans to "amanaplanacanalpanama"
Input: "race a car"
Output: false
Why: cleans to "raceacar"
Input: " "
Output: true
Why: cleans to "" — an empty string is a palindromeIntuition
The simplest correct approach is two steps: build a cleaned string, then compare it with its reverse. That is easy to write and uses O(n) extra space.
The key insight
You do not need the cleaned string. Walk two pointers inward from both ends of the original string:
- Skip anything that is not a letter or digit.
- Compare the two characters case-insensitively.
- Any mismatch means it is not a palindrome.
The cleaning happens implicitly, as a skip rule, so no second string is ever built.
Real-world analogy
Two people checking that a long banner reads the same from both ends. One starts at the left, one at the right, both walking toward the middle. Each ignores punctuation and spaces, calling out only real characters. If every called-out pair matches, the banner is a palindrome.
Watch it run
Approach
While left < right
Advance left past non-alphanumeric characters, and retreat right past them.
Compare, case-insensitively
If they differ, return false.
Move both inward and repeat
If the loop finishes, return true.
Guard the skip loops with `left < right`
Writing while not s[left].isalnum(): without the bounds check runs off the end of an all-punctuation string like ",.;". Every inner skip loop needs the same left < right condition as the outer loop.
Solution
def is_palindrome(s: str) -> bool:
"""True if s reads the same both ways, ignoring case and punctuation."""
left, right = 0, len(s) - 1
while left < right:
# Skip anything that is not a letter or digit.
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 += 1
right -= 1
return TrueThe two-step version, if readability matters more than memory:
def is_palindrome_simple(s: str) -> bool:
cleaned = "".join(char.lower() for char in s if char.isalnum())
return cleaned == cleaned[::-1]A note on `isalnum` across languages
Python's str.isalnum() is Unicode-aware — "é".isalnum() is True. The regex /[a-z0-9]/i is ASCII-only.
For this problem the input is guaranteed ASCII, so both work. For real-world text the difference matters, and you would use \p{L}\p{N} with the u flag in JavaScript.
Complexity Analysis
Time Complexity
O(n)
Space Complexity
O(1)
- Time — each pointer moves monotonically toward the middle, so every character is examined at most once.
- Space — two indices. The two-step version is also
O(n)time but usesO(n)space for the cleaned string and its reverse.
Edge Cases
Related Problems
- Longest Palindrome — building a palindrome from character counts
- Palindrome Number — the same test on digits, without converting to a string
- Container With Most Water — converging two pointers on an array