Valid Palindrome
Problem statement
Given a string s, check whether it reads the same forwards and backwards once you ignore case and drop everything that isn't a letter or digit — punctuation, spaces, colons, all of it. Return true if it does.
Think of it as sanity-checking a value that should be symmetric, like a checksum or a palindrome-shaped identifier, while ignoring formatting characters someone added for readability.
Examples
Example 1
Input: s = "A man, a plan, a canal: Panama"
Output: true
Explanation: Stripping punctuation and spaces and lowercasing everything gives "amanaplanacanalpanama", which reads the same both ways.
Example 2
Input: s = "race a car"
Output: false
Explanation: Cleaned up, this is "raceacar" — the second letter from the start is "a" but the second from the end is "a" too, yet the third pair ("c" vs "a") doesn't match.
Hints
Approach
Optimal: Two pointers
Intuition
You don't need a cleaned copy to check symmetry — you need to compare the first meaningful character with the last meaningful character, then the second with the second-to-last, and so on. Keep one pointer at the very start and one at the very end. Skip a pointer inward past any character that isn't a letter or digit. Compare the two characters the pointers land on; if they don't match (ignoring case), it's not a palindrome. Otherwise step both pointers inward and repeat.
This does the same comparisons as the brute-force version but never builds a second string, which is what drops the space from O(n) to O(1).
Steps
- Set
left = 0andright = len(s) - 1. - While
left < right:- Move
leftforward while it points at a character that isn't a letter or digit. - Move
rightbackward while it points at a character that isn't a letter or digit. - If the lowercase characters at
leftandrightdiffer, returnfalse. - Move
leftforward one step andrightbackward one step.
- Move
- If the loop finishes without a mismatch, return
true.
Dry run
s = "race a car" (spaces are not letters or digits, so they're skipped)
| left | right | s[left] | s[right] | match? |
|---|---|---|---|---|
0 (r) |
9 (r) |
r | r | yes |
1 (a) |
8 (a) |
a | a | yes |
2 (c) |
6 (c) |
c | c | yes |
3 (e) |
4 (skip space) → 4 (a) |
e | a | no → return false |
Edge cases: a single space " " has left = 0 and right = 0 already, so the while left < right loop never runs and the function returns true immediately — an empty-after-cleaning string is vacuously a palindrome. A one-character string behaves the same way.
Complexity
Time O(n) - each pointer only moves inward and never backtracks, so together `left` and `right` visit each character at most once, for O(n) total work.
Space O(1) - only the two integer pointers are kept; the function never builds a second string, so memory use doesn't grow with the size of the input.
class Solution:
def isPalindrome(self, s: str) -> bool:
left, right = 0, len(s) - 1
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 += 1
right -= 1
return True
if __name__ == "__main__":
print(str(Solution().isPalindrome("A man, a plan, a canal: Panama")).lower()) # true
print(str(Solution().isPalindrome("race a car")).lower()) # false
print(str(Solution().isPalindrome(" ")).lower()) # trueRecapThe whole problem in a few lines, for the night before
- Spot it: palindrome check that ignores case, spaces and punctuation
- Idea: two pointers from both ends; skip anything that is not a letter or digit, then compare lowercase
- Cost: O(n) time, O(1) space
- Trap: keep the pointers in bounds while skipping; an empty or symbols-only string is a palindrome
Interview follow-ups
What if you also had to return the cleaned string, not just true/false?
You'd need to build it, which brings back the O(n) space the two-pointer trick avoided — there's no way to hand back the cleaned string without storing it somewhere. Build it once with the same one-pass filter-and-lowercase logic from the brute-force approach, and compare it to its reverse as before.
The string could be a live stream (e.g. arriving over a socket) instead of a fixed array. How would that change your approach?
Two pointers from both ends need random access to the whole string up front, which a stream doesn't give you. You'd instead buffer the stream into a string as it arrives (or use a deque and pop from both ends once the whole message is buffered), so the algorithm doesn't change — only the fact that you must wait for the full input before starting the pointer walk.
Frequently asked questions
It never builds a second string. It only ever looks at two positions in the original string at a time, so the only extra memory it needs is the two integer pointers — that's O(1) regardless of how long the string is.
The problem defines "alphanumeric" using ASCII letters and digits, and the standard isalnum/Character.isLetterOrDigit checks follow that. An accented letter like "é" is not treated as alphanumeric by these checks, so it's skipped just like punctuation — worth calling out explicitly if you're asked to extend this to full Unicode text.
Two pointers scanning inward from both ends is the same shape as comparing a request and response checksum, validating that a config value is mirrored correctly, or checking a log line is well-formed from both edges — it's a cheap way to test whether you reach for O(1)-space techniques instead of defaulting to extra memory.
