Valid Palindrome
Maintained by Vikas D, software engineer
You are given a string that may contain letters, digits, spaces, and punctuation. The goal is to test whether it is a palindrome, but only the alphanumeric characters count. Every space, comma, colon, underscore, or other symbol is ignored entirely.
Comparison is case insensitive, so an uppercase 'A' and a lowercase 'a' are considered the same character. After filtering and lowercasing, the remaining sequence must be identical when read left to right and right to left.
Return true when that filtered sequence is a palindrome and false otherwise. A string with no alphanumeric characters at all (including an empty string) counts as a palindrome because there is nothing that breaks the symmetry.
Examples
Stripping non-alphanumerics and lowercasing gives 'amanaplanacanalpanama', which reads the same in both directions.
The cleaned form is 'raceacar'. The first character 'r' does not match the last character 'r' once you fold inward: 'raceacar' reversed is 'racaecar', so it is not a palindrome.
A single space has no alphanumeric characters, so the filtered string is empty and is treated as a palindrome.
The underscore is skipped, leaving 'aba', which is symmetric.
Constraints
- The input is a string that can be empty.
- Characters may include printable ASCII letters, digits, spaces, and punctuation.
- Only the characters [0-9a-zA-Z] are compared; everything else is ignored.
- Letter comparison ignores case.
Visible test cases
- isPalindrome("A man, a plan, a canal: Panama") == true
- isPalindrome("race a car") == false
- isPalindrome(" ") == true
- isPalindrome("ab_a") == true
Hints
Hint 1
First picture the simplest version: build a new string of just the lowercased letters and digits, then check it against its reverse.
Hint 2
You do not actually need a second copy of the string. Two indices, one at each end, can walk toward the middle and compare as they go.
Hint 3
When a pointer lands on a non-alphanumeric character, advance that pointer without comparing. Only compare when both pointers sit on alphanumeric characters.
Approaches
Filter then compare with reverse
Time O(n) · Space O(n)Reduce the messy input to a clean canonical form, then a palindrome check is trivial.
- Walk through the string and keep only characters that are letters or digits, lowercasing each one.
- Join those kept characters into a new string.
- Compare that string to its reverse and return whether they are equal.
Two pointers in place
Time O(n) · Space O(1)Compare from both ends inward while skipping characters that do not count, so no extra string is built.
- Set a left pointer at index 0 and a right pointer at the last index.
- While left is less than right, advance left past any non-alphanumeric character and move right back past any non-alphanumeric character.
- Compare the lowercased characters at left and right; if they differ, return false.
- Step both pointers one place inward and continue until they meet or cross, then return true.
Common mistakes
- Forgetting that an empty or all-punctuation string must return true rather than false.
- Treating the underscore as alphanumeric. In many built-in word-character checks '_' counts as a word character, but here only [0-9a-zA-Z] qualify, so 'ab_a' must skip the underscore.
- Comparing characters without lowercasing, which wrongly rejects inputs like 'Aa'.
- Letting a skip loop run past the other pointer; guard each inner skip with the left-less-than-right condition so the pointers cannot cross.
Follow-up variations
- What changes if you must also allow the string to be a palindrome after deleting at most one character?
- How would you handle full Unicode, where case folding and 'what counts as alphanumeric' are far more involved than ASCII?
- Could you stream the check over a very large input that does not fit in memory, comparing from both ends without loading it all at once?