Valid Palindrome
Understand the problem
You're given a string s. After converting all uppercase letters to lowercase and removing every non-alphanumeric character, check whether the remaining string is a palindrome — that is, it reads the same forward and backward.
Example:
s = "A man, a plan, a canal: Panama"
output = true // after cleaning: "amanaplanacanalpanama" — reads the same both ways
s = "race a car"
output = false // after cleaning: "raceacar" — not the sameThe Two Pointers technique works in place without building a new string — truly O(1) space.
Show the basic approach (slower)
O(n) time, O(n) spacefunction isPalindrome(s: string): boolean {
// Filter and normalize the string
const cleaned = s.toLowerCase().replace(/[^a-z0-9]/g, '')
return cleaned === cleaned.split('').reverse().join('')
}Build a cleaned string and a reversed string — each costs O(n) space.
Simple, but it uses memory you don't need.
Optimal solution
O(n) time, O(1) spacefunction isPalindrome(s: string): boolean {
let left = 0
let right = s.length - 1
while (left < right) {
// Skip non-alphanumeric characters
while (left < right && !isAlphanumeric(s[left])) left++
while (left < right && !isAlphanumeric(s[right])) right--
if (s[left].toLowerCase() !== s[right].toLowerCase()) return false
left++
right--
}
return true
}
function isAlphanumeric(ch: string): boolean {
const code = ch.charCodeAt(0)
return (code >= 48 && code <= 57) // 0-9
|| (code >= 65 && code <= 90) // A-Z
|| (code >= 97 && code <= 122) // a-z
}The optimal approach: two pointers move toward the middle, skipping invalid characters at each step.
- No new string is created — it works directly on the original string.
- Stop when the two pointers meet.
Step-by-step trace
1function isPalindrome(s: string): boolean {2 let left = 03 let right = s.length - 14 while (left < right) {5 // Skip non-alphanumeric characters6 while (left < right && !isAlphanumeric(s[left])) left++7 while (left < right && !isAlphanumeric(s[right])) right--8 if (s[left].toLowerCase() !== s[right].toLowerCase()) return false9 left++10 right--11 }12 return true13}14 15function isAlphanumeric(ch: string): boolean {16 const code = ch.charCodeAt(0)17 return (code >= 48 && code <= 57) // 0-918 || (code >= 65 && code <= 90) // A-Z19 || (code >= 97 && code <= 122) // a-z20}Edge cases to remember
Empty string — after filtering there are no characters, return true (an empty palindrome).
Only special characters "!!! ???" — empty after filtering, return true.
A single alphanumeric character "a" — left=right=0, the while (left < right) loop doesn't run, return true.
Non-alphanumeric characters interleaved with the letters: "A.,B" → cleaned "ab" → not a palindrome.