Learn › DSA Patterns › Two Pointers › Case Study
Valid Palindrome:
5 Bugs to a Clean Solution
Not a tutorial — a real debugging log. Six attempts, five distinct bugs, each one reproduced with a concrete failing input before it was fixed.
The Problem
LeetCode 125 — Valid Palindrome
A phrase is a palindrome if, after
converting all uppercase letters to lowercase 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.
Input
"A man, a plan, a canal: Panama" Output
true Input
"race a car" Output
false Input
" " Output
true The Journey
Attempt by Attempt
Every bug below was reproduced with a real failing input before being fixed — not just described.
function isPalindrome(s: string): boolean {
const filteredS = (s.replace(/[^a-zA-Z0-9]/g, "")).toLowerCase()
const reversedS = filteredS.split("").reverse("").join("")
if(filteredS===reversedS) return true
else return false
}TypeScript strict mode rejects the code before it even runs.
Array.prototype.reverse() takes zero arguments — but this passes an empty string to it. Plain JavaScript silently ignores the extra argument, but tsc --strict (which is effectively what LeetCode compiles against) does not.
Proof — tsc --strict --noEmit output:
error TS2554: Expected 0 arguments, but got 1.
Drop the argument: .reverse() instead of .reverse("").
function isPalindrome(s: string): boolean {
const filteredS = (s.replace(/[^a-zA-Z0-9]/g, "")).toLowerCase()
let i=0,j=filteredS.length-1
while(i<j) {
if(filteredS[i] !== filteredS[j]) {
break; return false
}
// ⚠ i and j are never advanced — infinite loop whenever chars match
}
return true
}Compiles fine, but is wrong in two independent ways.
First: i and j are never incremented or decremented, so once two characters match, the while(i < j) condition never changes — the loop spins forever. Second: break exits the loop immediately, so the return false right after it is unreachable dead code — mismatches silently fall through to return true at the bottom.
Proof — two different failing inputs:
isPalindrome("race a car") → hangs forever (would time out on LeetCode)
isPalindrome("ab") → true (WRONG — expected false) Add i++ / j-- inside the loop, and replace break; return false with just return false — return already exits the function.
function isPalindrome(s: string): boolean {
const filteredS = (s.replace(/[^a-zA-Z0-9]/g, "")).toLowerCase()
let i=0,j=filteredS.length-1
while(i<j) {
if(filteredS[i] !== filteredS[j]) {
return false;
}
i++
j--
}
return true
}Both bugs from Attempt 2 fixed: return false runs immediately on a mismatch, and the pointers advance every iteration. Verified against 8 hand-picked cases — including LeetCode's own examples — and tsc --strict compiles cleanly.
Proof — verification run:
"A man, a plan, a canal: Panama" → true ✅ "race a car" → false ✅ "0P" → false ✅ ".," → true ✅ (all-punctuation edge case)
function isPalindrome(s: string): boolean {
let i=0,j=s.length-1
while(i<j) {
if(/[^a-zA-Z0-9]/g.test(s[i])) i++
if(/[^a-zA-Z0-9]/g.test(s[j])) j--
if(s[i] !== s[j]) {
return false; break
}
i++
j--
}
return true
}
// ⚠ compares raw s (no lowercasing) — and a single "if" only skips ONE bad charTwo new bugs while optimizing away the filteredS copy.
This drops the pre-filtered string to save space, skipping bad characters inline instead. But it compares raw s[i]/s[j] — no lowercasing — and each side only skips ONE non-alphanumeric character per loop iteration (a single if, not a loop), so runs of two or more punctuation characters in a row aren't fully skipped.
Proof — targeted failing inputs:
isPalindrome("A man, a plan, a canal: Panama") → false (WRONG — expected true)
isPalindrome("Aa") → false (WRONG — expected true) Needs both: lowercase before comparing, and while-loops (not if) to skip runs of bad characters.
function isPalindrome(s: string): boolean {
const filteredString = s.toLowerCase();
let i=0,j=filteredString.length-1
while(i<j) {
while(/[^a-zA-Z0-9]/g.test(filteredString[i])) ++i
while(/[^a-zA-Z0-9]/g.test(filteredString[j])) --j
if(s[i] !== s[j]) {
return false; break
}
i++
j--
}
return true
}
// ⚠ while-loops fix the multi-char skip, but this still reads from raw `s`, not `filteredString`The skip logic is now solid — but the case bug moved, it didn't disappear.
Switching to while fixed the multi-character skip issue entirely: a 200,000-case randomized fuzz test against a reference implementation found zero pointer-crossing bugs. But the final comparison still reads from the original s instead of the lowercased filteredString, so every mixed-case input still fails.
Proof — fuzz test findings (200,000 random trials):
COUNTEREXAMPLE: "aA" got: false expected: true COUNTEREXAMPLE: "aB ba," got: false expected: true COUNTEREXAMPLE: "baaAb" got: false expected: true (0 crossing-pointer bugs found — only case-sensitivity failures)
Compare filteredString[i] vs filteredString[j] — not s[i] vs s[j].
function isPalindrome(s: string): boolean {
const filteredString = s.toLowerCase();
let i = 0, j = filteredString.length - 1;
while (i < j) {
while (/[^a-zA-Z0-9]/.test(filteredString[i])) i++;
while (/[^a-zA-Z0-9]/.test(filteredString[j])) j--;
if (filteredString[i] !== filteredString[j]) return false;
i++;
j--;
}
return true;
}One-line fix: compare the lowercased filteredString instead of the original s. Re-ran the same 200,000-case fuzz test plus tsc --strict — zero mismatches, clean compile.
Proof — final verification:
FUZZ: 0 mismatches in 200,000 trials — VERIFIED CORRECT tsc --strict --noEmit final.ts → clean compile, no errors
Lessons Learned
Key Takeaways
TypeScript strict mode catches what JS silently swallows
Array.prototype.reverse("") runs fine in plain JavaScript — the extra argument is just ignored. tsc --strict flags it as TS2554. LeetCode compiles under TypeScript, so this bug only shows up there.
return already exits — break right after it is dead code
break; return false looks harmless but break fires first and exits the loop before return ever runs. Any code immediately after return in the same statement position is unreachable.
Two-pointer loops must strictly advance both pointers
A while (i < j) loop that never changes i or j runs forever the moment its exit condition (a mismatch) doesn't trigger. This is an easy bug to miss because it only manifests as a hang, not a wrong answer.
Normalize case at the exact comparison site
Building a lowercased filteredString doesn't help if the comparison line still reads from the original s. The same case-sensitivity bug resurfaced in a completely different spot in Attempt 5 for exactly this reason.
Skipping invalid characters needs a while, not a single if
An if only skips one character per loop pass. Runs of two or more consecutive non-alphanumeric characters (like ",," or " .") need a while loop that keeps skipping until it lands on a valid character.
Final Result
Two Verified Solutions
Both pass every test case in this journey — pick based on the space constraint.
// O(N) space — filter + reverse + compare
function isPalindrome(s: string): boolean {
const filteredS = s.replace(/[^a-zA-Z0-9]/g, "").toLowerCase();
let i = 0, j = filteredS.length - 1;
while (i < j) {
if (filteredS[i] !== filteredS[j]) return false;
i++;
j--;
}
return true;
}// O(1) extra space — skip invalid chars inline, no filtered copy
function isPalindrome(s: string): boolean {
const filteredString = s.toLowerCase();
let i = 0, j = filteredString.length - 1;
while (i < j) {
while (/[^a-zA-Z0-9]/.test(filteredString[i])) i++;
while (/[^a-zA-Z0-9]/.test(filteredString[j])) j--;
if (filteredString[i] !== filteredString[j]) return false;
i++;
j--;
}
return true;
}| Solution | Time | Space | Verified |
|---|---|---|---|
| Filter + Compare (Attempt 3) | O(N) | O(N) | 8 hand-picked cases + tsc |
| Inline Skip (Attempt 6) Optimized ✓ | O(N) | O(1) | 200,000-case fuzz test + tsc |
Keep Learning
Bugs are part of the process 🎉
Five real bugs, five real fixes — that's what getting to a correct, optimized solution actually looks like.