Valid Palindrome: The Two-Pointer Approach
The Prompt
A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Given a string `s`, return `true` if it is a palindrome, or `false` otherwise.
Understanding the Problem
Strip everything that is not alphanumeric, lowercase what remains, and ask whether the string reads the same both ways. The naive way builds the cleaned string and compares it to its reverse — correct, but O(n) extra space.
Two pointers do the same comparison in place: one from each end, skipping the junk characters as they walk.
The Interview Flow
Interviewer
Your task is to determine if a given string is a palindrome, considering only alphanumeric characters and ignoring case.
Candidate
Okay. So I should first process the string to keep only letters and numbers, and convert everything to the same case, say, lowercase. Then I can check if the resulting string is a palindrome.
Interviewer
How would you check if the cleaned string is a palindrome?
Candidate
I could reverse the cleaned string and see if it equals the original cleaned string. But that would use extra space. A better way is to use the two-pointer technique.
Interviewer
Explain the two-pointer approach.
Candidate
I would set one pointer at the beginning of the string and another at the end. I would then move them towards the center, comparing the characters they point to. If at any point the characters do not match, it's not a palindrome. I should also handle skipping non-alphanumeric characters as I move the pointers.
Interviewer
That sounds efficient. Please implement it.
Why do two pointers suffice?
A palindrome is a symmetric claim: position k must mirror position n−1−k. Checking the outermost pair first and walking inward tests every mirrored pair exactly once — any mismatch ends it immediately.
Skipping non-alphanumeric characters inside the loop (instead of pre-cleaning) is what earns the O(1) space answer.
In-Place Solution with Two Pointers
- Initialize two pointers, `left` at the beginning of the string (index 0) and `right` at the end (index `length - 1`).
- Loop as long as `left` is less than `right`.
- Inside the loop, move the `left` pointer to the right until it points to an alphanumeric character.
- Similarly, move the `right` pointer to the left until it points to an alphanumeric character.
- Compare the characters at the `left` and `right` pointers, after converting them to lowercase. If they are not the same, the string is not a palindrome, so return `false`.
- If they match, move both pointers towards the center: increment `left` and decrement `right`.
- If the loop finishes, it means all characters matched, and the string is a palindrome. Return `true`.
Try it yourself
Write your solution and run it against 3 test cases.
JavaScript, TypeScript & Python run sandboxed in your browser; other languages run on the execution server. Your code is saved locally as you type.
Final Solution
function isPalindrome(s) {
let left = 0;
let right = s.length - 1;
while (left < right) {
while (left < right && !/[a-zA-Z0-9]/.test(s[left])) {
left++;
}
while (left < right && !/[a-zA-Z0-9]/.test(s[right])) {
right--;
}
if (s[left].toLowerCase() !== s[right].toLowerCase()) {
return false;
}
left++;
right--;
}
return true;
}Explanation
Check "racecar" — pointers meet in the middle without ever disagreeing.
1l = 0, r = 6: 'r' vs 'r' — match. Walk both inward.
2'a' vs 'a', then 'c' vs 'c' — every mirrored pair agrees.
3Pointers meet at the center: nothing left to compare, so the string is a palindrome.
Complexity Analysis
TIME
O(n)
SPACE
O(1)
Finished working through this one?
Mark it complete to track it on your Data Structures path.