March 24
Valid Palindrome
How to notice that the problem asks for mirrored comparison, not a pile of unnecessary preprocessing.
Strings and Two Pointers Beginner 12 min TypeScript
Given a string s, return true if it is a palindrome when considering only alphanumeric characters and ignoring differences between uppercase and lowercase letters.
Example:
Input: s = "A man, a plan, a canal: Panama"
Output: true
What to notice before coding
- Spaces, punctuation, and symbols must be ignored.
- Palindrome comparison always happens from the outside toward the center.
- Lowercasing avoids false mismatches caused by casing only.
Common mistakes
- forgetting to skip non-alphanumeric characters before comparing
- cleaning the whole string without noticing the same answer fits in [O(1)](/glossary/o-one) extra space
Step 1 — Understand what must be ignored
If you compare the raw string directly, you will get the wrong answer.
The prompt tells you to ignore:
- spaces
- punctuation
- case differences
So the real question is not "is the original string equal to its reverse?".
The real question is:
after ignoring what does not matter, does the left side match the right side?
Step 2 — Write the first correct version
A simple baseline is to build a cleaned version of the string and compare it with its reverse:
export function isPalindrome(s: string): boolean {
const cleaned = s.toLowerCase().replace(/[^a-z0-9]/g, '')
return cleaned === cleaned.split('').reverse().join('')
}
It works. But it creates one new string and then another for the reversed value.
Step 3 — Ask what really needs to be compared
A palindrome is always a mirrored comparison:
- first against last
- second against second-last
- and so on
That already suggests two pointers.
Step 4 — Clean on demand
Instead of cleaning everything first, skip invalid characters only when needed.
That means:
leftmoves to the rightrightmoves to the left- both skip non-alphanumeric characters
- when they stop, compare them
The interactive editor needs JavaScript. You can still read the prompt and copy the starter code below.
Starter code
export function isPalindrome(s: string): boolean {
// your solution here
return false
}
Haven't solved it yet?
Viewing the solution now may reduce learning. It's worth trying a bit more.
Open the reference solution
Without JavaScript, the reference solution is shown inline instead of in a dialog.
Solution
Final complexity
Time: O(n)
Space: O(1)
Solution 1 — Clean and compare O(n) with extra memory
This is a good baseline.
export function isPalindrome(s: string): boolean {
const cleaned = s.toLowerCase().replace(/[^a-z0-9]/g, '')
return cleaned === cleaned.split('').reverse().join('')
}Simple. But it uses memory you do not really need.
Solution 2 — Two pointers O(n) and O(1) extra space
If the comparison goes from the edges toward the center, use two pointers and skip what does not matter.
function isAlphaNumeric(char: string): boolean {
return /[a-z0-9]/i.test(char)
}
export function isPalindrome(s: string): boolean {
let left = 0
let right = s.length - 1
while (left < right) {
while (left < right && !isAlphaNumeric(s[left])) {
left += 1
}
while (left < right && !isAlphaNumeric(s[right])) {
right -= 1
}
if (s[left].toLowerCase() !== s[right].toLowerCase()) {
return false
}
left += 1
right -= 1
}
return true
}You only compare what matters and keep the original string as your source of truth.
What to say in the interview
A strong short explanation would be:
The baseline cleans the string and compares it with its reverse, which works in
O(n)but uses extra memory. Since palindrome checking is a mirrored comparison, I can use two pointers, skip invalid characters on demand, and keepO(1)extra space.
That shows that you:
- understood the simple version first
- turned the rule into pointer movement
- justified the improvement without making the solution harder to follow
When this pattern shows up again
The same pattern comes back when you need to:
- compare opposite ends
- move toward the center
- ignore parts of the input while scanning
- validate symmetry without building new structures
The point is not memorizing “palindrome = two pointers”.
The point is noticing when the problem naturally pushes you to compare edges.