Valid Palindrome
Decide whether a string reads the same both ways once you ignore case and anything that is not a letter or digit. A warm-up for two pointers moving toward each other. Solve it below in Python or JavaScript, then read the walkthrough.
Problem
You're given a string s. Decide whether it's a palindrome when you only look at its letters and digits, treating uppercase and lowercase letters as equal. Spaces, punctuation, and every other character are ignored.
Return true if the filtered string reads the same forward and backward, and false otherwise. A string with no letters or digits at all counts as a palindrome.
Example 1
- Input
- s = "Top spot."
- Output
- true
Keeping only letters and lowering the case gives "topspot", which is the same reversed.
Example 2
- Input
- s = "Rotor, motor"
- Output
- false
The filtered string is "rotormotor", and its reverse is "rotomrotor".
Example 3
- Input
- s = " "
- Output
- true
Nothing is left after filtering, and an empty string is a palindrome.
Constraints
- 1 ≤ s.length ≤ 2 × 10⁵
- s contains printable ASCII characters only.
Practice
Runs 14 tests in your browser. Python loads on the first run (about 6 MB, then cached). Press ⌘/Ctrl + Enter to run.
Get asked Valid Palindrome in a real interview?
Interview Solver gives you a working solution live, during your actual coding interview. Invisible to screensharing.
How to solve Valid Palindrome
Pattern: Two pointers from both ends
A palindrome check is a comparison between position i from the front and position i from the back. Two pointers, one at each end, moving inward, do exactly that without building a reversed copy.
The filtering rule just changes how the pointers move: before comparing, slide each pointer past any character that isn't a letter or digit. Then compare the two characters case-insensitively. If they ever differ, it's not a palindrome. If the pointers meet or cross, every pair matched.
Approach 1: Filter, then compare with the reverse
Build a new string of only the lowercased letters and digits, then check whether it equals its reverse. Short and readable, but it allocates two extra strings of up to n characters.
Time O(n) · Space O(n)
Approach 2: Two pointers that skip non-alphanumerics
Set left = 0 and right = n - 1. While left < right:
- Move
leftforward while it points at a non-alphanumeric character (andleft < right). - Move
rightbackward the same way. - If the lowercase forms of
s[left]ands[right]differ, returnfalse. - Step both pointers inward.
Return true when the loop ends. No copies are made.
Time O(n) · Space O(1)
| Approach | Time | Space |
|---|---|---|
| Filter, then compare with the reverse | O(n) | O(n) |
| Two pointers that skip non-alphanumerics | O(n) | O(1) |
Solution code
Try the practice editor first. Both solutions pass every test above.
Valid Palindrome solution in Python
def is_palindrome(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 TrueValid Palindrome solution in JavaScript
function isPalindrome(s) {
const isAlnum = (ch) => /[a-z0-9]/i.test(ch);
let left = 0;
let right = s.length - 1;
while (left < right) {
while (left < right && !isAlnum(s[left])) left++;
while (left < right && !isAlnum(s[right])) right--;
if (s[left].toLowerCase() !== s[right].toLowerCase()) return false;
left++;
right--;
}
return true;
}Common mistakes
- Filtering out digits along with punctuation. Digits count, so "7x" is not a palindrome.
- Forgetting the `left < right` guard in the skipping loops, which runs a pointer off the end on strings like ".,;!".
- Comparing without normalizing case, so "Aa" is wrongly rejected.
- Returning false for a string with no letters or digits. It filters down to the empty string, which is a palindrome.
What interviewers look for
Mention the filter-and-reverse version first since it's a one-liner, then say you can drop the extra memory with two pointers. Interviewers like to see that you know both and can explain the trade-off.
When you write the pointer version, call out the bounds check inside the skip loops. It's the one line people forget, and tracing a punctuation-only string shows you've considered it.
Follow-up questions
What if you may delete at most one character to make it a palindrome?
Run the same two pointers. At the first mismatch, check whether skipping the left character or skipping the right character leaves a palindrome in the remaining range. Each check is linear, so the total is still O(n).
How would you handle full Unicode text?
Use a Unicode-aware alphanumeric test and case folding (`str.casefold()` in Python) rather than ASCII rules. Combining marks and characters outside the basic plane need care, so you may compare normalized grapheme clusters instead of code units.
What if the string is streamed and too large to hold?
A palindrome check needs the end to compare with the start, so a true one-pass check without memory is impossible. A rolling hash computed forward and backward gives a probabilistic answer in O(1) memory.
Companies that ask Valid Palindrome
Valid Palindrome is tagged by 137 companies in our interview dataset. The score shows how often it comes up at each company.
- AT&T100%
- West Monroe100%
- Zenefits100%
- Narvar100%
- Amplitude100%
- Domo100%
- Cadence Design Systems100%
- Zulily95%
- Nylas93%
- Carta93%
- LTI92%
- Stitch Fix89%
- Klarna87%
- Liberty Mutual86%
- Appian84%
- Xandr84%
- Comcast83.3%
- Maxim Integrated83%
- Willowtree83%
- Meta82.6%
- Zego82%
- Liberty It82%
- Saif81%
- Integral Ad Science80%
and 113 more.
Practice next
Get live help in the real interview
Working solutions in real time during your actual interview. Invisible to screensharing.
Start Free TrialNo credit card required