Valid Palindrome — Two-Pointer Scan Ignoring Non-Alphanumerics
Move pointers inward while skipping non-alphanumeric characters; compare lowercased characters for equality.
Problem Statement
Given a string, determine if it is a palindrome considering only alphanumeric characters and ignoring cases.
Why This Problem Matters
- Fundamental two-pointer technique on strings.
- Introduces character classification and case normalisation.
- Common warm-up before more nuanced string manipulation questions.
Thought Process
Filter on the fly
Instead of allocating a filtered string, skip non-alphanumeric characters during pointer movement.
Normalise case
Compare characters in lowercase (or uppercase) to make the check case-insensitive.
Stop when pointers cross
If at any point characters mismatch, return false; otherwise true when loop completes.
Step-by-Step Reasoning
- Initialise left = 0 and right = s.length() - 1.
- Advance left while s[left] not alphanumeric; decrement right for same condition.
- Compare Character.toLowerCase(s.charAt(left)) and right counterpart; return false if unequal.
- Move pointers inward and repeat until left >= right; return true.
Dry Run
s = "A man, a plan, a canal: Panama"
Pointers skip punctuation and match letters; returns true.
s = "race a car"
Mismatch between letters c and a triggers false.
Complexity Analysis
Time
O(n)
Space
O(1)
Why
Two pointers each traverse string once; no extra allocations required.
Annotated Solution
public class ValidPalindrome {
public boolean isPalindrome(String s) {
int left = 0;
int right = s.length() - 1;
while (left < right) {
while (left < right && !Character.isLetterOrDigit(s.charAt(left))) {
left += 1;
}
while (left < right && !Character.isLetterOrDigit(s.charAt(right))) {
right -= 1;
}
if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) {
return false;
}
left += 1;
right -= 1;
}
return true;
}
}The two-pointer scan skips irrelevant characters and compares case-insensitive letters in O(1) memory.
Common Pitfalls
- Creating a filtered copy costs O(n) space; mention but prefer in-place pointers.
- Forgetting to handle empty string; should return true.
- Not using Character.isLetterOrDigit can mis-handle Unicode; clarify scope with interviewer.
Follow-Up Questions
- How would you extend this to ignore diacritics or handle Unicode normalisation?
- Can you check near-palindromes that allow one deletion?