Check a string is a palindrome in O(n) time, O(1) space
Implement isPalindrome(s) that returns true when s reads the same forwards and backwards, ignoring case and any character that is not a letter. Requirements: O(n) time and O(1) extra space — scan with two pointers from both ends, do not build a cleaned copy of the string. 'A man, a Plan!' is NOT a palindrome but 'Madam' and '' are.
function isPalindrome(s) {
// your code here
}Write the implementation.
Two pointers l = 0 and r = s.length - 1 move inward. Skip any side whose character fails a letter test (e.g. a regex like /[a-z]/i), then compare with toLowerCase; a mismatch returns false. Meeting in the middle returns true. This is O(n) time and O(1) extra space — no cleaned copy is built.
- ✗Building a cleaned or reversed copy, which costs O(n) extra space instead of O(1)
- ✗Comparing characters without lowercasing both sides first
- ✗Forgetting to skip non-letters on BOTH sides before each comparison
- →How would you also treat digits as significant characters?
- →Why does skipping non-letters inside the loop keep it O(n) overall?
Solution
Two pointers start at the ends and converge toward the middle, skipping non-letters.
function isPalindrome(s) {
const isLetter = (c) => /[a-z]/i.test(c);
let l = 0, r = s.length - 1;
while (l < r) {
if (!isLetter(s[l])) { l++; continue; } // skip on the left
if (!isLetter(s[r])) { r--; continue; } // skip on the right
if (s[l].toLowerCase() !== s[r].toLowerCase()) return false;
l++;
r--;
}
return true;
}How it works
The pointers move from both ends toward the middle. Before comparing a pair of characters, each pointer is advanced past anything that is not a letter, so punctuation and spaces never affect the result. The comparison lowercases both characters, so case is ignored.
Any mismatch returns false immediately. If the pointers meet, the string is a palindrome. Each character is visited at most once, giving O(n) time and O(1) space — no cleaned copy is allocated. The empty string runs the loop zero times and correctly returns true. </content>
