Valid Palindrome
EasyTwo pointers
A phrase counts as a palindrome if, after you lowercase every letter and remove everything that is not a letter or a digit, it reads the same forwards and backwards.
Given a string s, return true if it is a palindrome and false otherwise.
Examples
Input: s = "Was it a car or a cat I saw?" Output: true
Cleaned up, it is wasitacaroracatisaw, the same both ways.
Input: s = "race a cat" Output: false
raceacat backwards is tacaecar.
Constraints
1 ≤ s.length ≤ 2 × 10⁵sis printable ASCII: letters, digits, spaces and punctuation.
Stuck?
Hint 1
You do not need to build the cleaned-up string. Start one pointer at each end.
Hint 2
Skip anything that is not a letter or a digit, compare the two characters in lowercase, and move both pointers inward.
The idea
A palindrome mirrors itself: its first character matches its last, its second matches the one before the last, and so on. Walk one pointer in from each end, skip anything that is not a letter or a digit, and compare the pairs. That checks the cleaned-up string without ever building it.
Time O(n)Extra space O(1)
Try it again with the idea in mind, or go through the code one step at a time.
The code, step by step
Step 1 of 5
Only letters and digits count. The i flag on the pattern lets it match capital letters too.
function isPalindrome(s) { const isLetterOrDigit = (c) => /[a-z0-9]/i.test(c); let left = 0; let right = s.length - 1; while (left < right) { if (!isLetterOrDigit(s[left])) left++; else if (!isLetterOrDigit(s[right])) right--; else if (s[left].toLowerCase() !== s[right].toLowerCase()) return false; else { left++; right--; } } return true;}The trap
It removes every character outside a-z and 0-9 without lowercasing first, so capital letters are deleted instead of lowered. A phrase that starts with a capital loses that letter while its mirror at the other end stays, and a real palindrome is called false. A capital that should break a palindrome disappears too, so a string that is not one can pass.
function isPalindrome(s) { const clean = s.replace(/[^a-z0-9]/g, ''); // forgot to lowercase first return clean === [...clean].reverse().join('');}