Valid Palindrome
Decide whether a sentence reads the same forwards and backwards once you ignore spaces, punctuation and capital letters.
- Converging two pointers
Before this, know: Strings and indexes, Loops (while)
A palindrome is a word or sentence that reads the same forwards and backwards, like “level” or “racecar”.
You get a string s (a piece of text). Return true if it is a palindrome and
false if it isn’t. There’s a twist: before checking, we ignore everything
that isn’t a letter or a digit (spaces, commas, !, : …), and we treat
capital and small letters as the same (“T” counts as “t”).
A string is really just a row of characters, each with an index (its
position, starting at 0). Here is s = "Taco cat!":
- T0
- a1
- c2
- o3
- ␣4
- c5
- a6
- t7
- !8
(We draw a space as ␣ so you can see it.) The rules that matter:
- Only letters and digits count. Digits matter too:
"0P"is not a palindrome. - Upper and lower case are the same letter.
- A string with no letters or digits at all (like
" ") counts as a palindrome. An empty string reads the same both ways.
Those two fingers are what programmers call pointers: variables that
remember a position in the string. We’ll call them left and right.
- l0
- e1
- v2
- e3
- l4
Pause and think
After the first match they move to index 1 and index 3 (both “e”). Then to
index 2 and index 2: they meet on the middle “v”. We stop as soon as left
is no longer smaller than right, because a single middle letter always matches
itself, so there is nothing left to compare.
The most direct idea: build a new string that keeps only the letters and digits (in lowercase), then check whether that string equals its own reverse.
Clean, reverse, compare
s = "Taco cat!"
- T0
- a1
- c2
- o3
- ␣4
- c5
- a6
- t7
- !8
- empty
- Looking at now
- Left out
- Just copied
- Same in both copies
- Different
Plan: copy only the letters and digits into a new string called "cleaned" (in lowercase), then compare it with its own reverse.
Which line is running?
function isPalindrome(s) { let cleaned = "";Running now: for (const ch of s) { if (/[a-z0-9]/i.test(ch)) { cleaned += ch.toLowerCase(); // keep letters and digits only } } const reversed = cleaned.split("").reverse().join(""); return cleaned === reversed;}Clean, reverse, compare
function isPalindrome(s) { let cleaned = ""; for (const ch of s) { if (/[a-z0-9]/i.test(ch)) { cleaned += ch.toLowerCase(); // keep letters and digits only } } const reversed = cleaned.split("").reverse().join(""); return cleaned === reversed;}def is_palindrome(s): cleaned = "" for ch in s: if ch.isalnum(): cleaned += ch.lower() # keep letters and digits only reversed_text = cleaned[::-1] return cleaned == reversed_textThis gives the right answer, and in an interview it’s a perfectly good first
thing to say. In Python, cleaned[::-1] is a short way to write “the string
backwards”.
It’s not slow: we read every character a few times, so the work grows in step
with the length of the string. We describe that with Big-O notation, a way to
say how work grows with input size: this is O(n) time,
where n is the number of characters.
The cost is memory. We build two brand-new strings: cleaned and its
reverse. For "Taco cat!" that’s 7 + 7 = 14 extra characters. For a string
of 200,000 characters (LeetCode’s limit), it can be 400,000 extra characters.
That’s O(n) extra space. The interviewer will
usually ask: “Can you do it without making a copy?”
Instead of copying, we can read the original string from both ends at the same time, skipping the characters that don’t count as we go.
Pattern
Converging two pointers
Use it when: you need to compare or pair up items from both ends of an array or string, such as checking symmetry.
Signal words
- “palindrome”
- “reads the same backward”
- “reverse”
- “compare from both ends”
- “in-place, O(1) extra space”
- Put
lefton index 0 andrighton the last index. - While
leftis smaller thanright: - Move
leftto the right past anything that isn’t a letter or digit. Do the same forright, moving left. - Compare
s[left]ands[right]in lowercase. If they differ, returnfalse. - If they match, move both pointers one step inward and repeat.
- If the loop ends, every pair matched: return
true.
Press Play, or click the player and use the arrow keys. Watch the grey boxes:
those are characters we skip without ever copying anything. Then try the
edge cases: a string that is only a space, and "0P", where a digit decides the answer.
Two pointers from both ends
s = "Taco cat!"
- T0
- a1
- c2
- o3
- ␣4
- c5
- a6
- t7
- !8
- left
- 0
- right
- 8
- s[left] vs s[right]
- —
- result
- —
- Skipped (not a letter or digit)
- Pair matches
- Pair differs / being skipped
- Already matched
Put one pointer on each end: left at index 0 and right at index 8. A palindrome reads the same from both ends, so we compare the outside pair first and walk inward.
Which line is running?
function isPalindrome(s) { let left = 0;Running now: let right = s.length - 1; while (left < right) { while (left < right && !isAlnum(s[left])) left++; // skip junk on the left while (left < right && !isAlnum(s[right])) right--; // skip junk on the right if (s[left].toLowerCase() !== s[right].toLowerCase()) { return false; } left++; // they match: move both pointers inward right--; } return true;}function isAlnum(ch) { return /[a-z0-9]/i.test(ch); // a letter or a digit?}Notice that the skipping loops also check left < right. Without that check, a
string made only of punctuation would let left run off the end of the string.
Two pointers from both ends
function isPalindrome(s) { let left = 0; let right = s.length - 1; while (left < right) { while (left < right && !isAlnum(s[left])) left++; // skip junk on the left while (left < right && !isAlnum(s[right])) right--; // skip junk on the right if (s[left].toLowerCase() !== s[right].toLowerCase()) { return false; } left++; // they match: move both pointers inward right--; } return true;}function isAlnum(ch) { return /[a-z0-9]/i.test(ch); // a letter or a digit?}def is_palindrome(s): left, right = 0, len(s) - 1 while left < right: while left < right and not s[left].isalnum(): left += 1 # skip junk on the left while left < right and not s[right].isalnum(): right -= 1 # skip junk on the right if s[left].lower() != s[right].lower(): return False left += 1 # they match: move both pointers inward right -= 1 return TrueOn LeetCode, JavaScript gives you var isPalindrome = function(s) { … } and
Python wraps the function in class Solution as def isPalindrome(self, s).
The body is the same as ours.
- Line 1: define the function. It takes the string
s. - Lines 2–3 (JS) / line 2 (Python): the two pointers.
leftstarts on the first character (index 0) andrighton the last one (indexlength − 1, because indexes start at 0). - Line 4 (JS) / line 3 (Python): keep going while
leftis still to the left ofright. When they meet or cross, every pair has been compared. - Line 5 (JS) / lines 4–5 (Python): skip characters on the left that
aren’t letters or digits.
isAlnumis our small helper at the bottom (JS, lines 16–18):/[a-z0-9]/iis a pattern that matches one letter or digit, and theimeans “ignore case”. In Python, strings already have.isalnum()(“is alphanumeric”, meaning a letter or a digit). - Line 6 (JS) / lines 6–7 (Python): the same skipping on the right side.
- Line 7 (JS) / line 8 (Python): compare the two characters in lowercase
(
toLowerCase()/.lower()), so “T” and “t” count as equal. - Line 8 (JS) / line 9 (Python): one mismatch proves it’s not a
palindrome, so return
falsestraight away. - Lines 10–11: both languages. The pair matched, so move both pointers one step inward.
- Line 13 (JS) / line 12 (Python): the loop finished without a mismatch,
so the answer is
true.
Let’s trace s = "Taco cat!". Indexes: T=0, a=1, c=2, o=3, space=4, c=5, a=6,
t=7, !=8.
| step | left | right | what happens |
|---|---|---|---|
| 1 | 0 | 8 | s[8] = '!' is not a letter: right moves to 7 |
| 2 | 0 | 7 | compare 'T' and 't': equal (ignoring case), move inward |
| 3 | 1 | 6 | compare 'a' and 'a': equal, move inward |
| 4 | 2 | 5 | compare 'c' and 'c': equal, move inward |
| 5 | 3 | 4 | s[4] is a space: right moves to 3 |
| 6 | 3 | 3 | left = right: 'o' matches itself, move inward |
| 7 | 4 | 2 | left > right: the loop stops, return true |
Step 5 is the interesting one: the space sits between the two halves. The right
pointer skips it and lands on the same spot as the left pointer, which is why
the skipping loop needs the left < right check.
Clean, reverse, compare
Time
O(n)
We read each character a constant number of times: once to clean, once to reverse, once to compare.
Space
O(n)
Two new strings, each up to n characters long.
Two pointers from both ends
Time
O(n)
Every step moves left or right closer to the other, so together they make at most n moves. Double the text, double the work.
Space
O(1)
Just two numbers, left and right, however long the string is. O(1) means 'a fixed amount'.
Both are equally fast; the two-pointer version wins on memory, and that’s the point interviewers are looking for.
What to say out loud, in this order:
- Confirm the rules: “Only letters and digits count, and case doesn’t matter?”
- Give the simple version first: “I could build a cleaned copy and compare it with its reverse. That’s O(n) time but O(n) extra space.”
- Improve it: “Instead, I’ll use two pointers from both ends and skip non-alphanumeric characters in place. Same O(n) time, O(1) space.”
- Mention the edge cases: digits, a string with no letters, and the pointers crossing.
Likely follow-up questions:
- “What if you may delete at most one character?” That’s Valid Palindrome II (LeetCode #680): on the first mismatch, try skipping the left character or the right one, and check the rest with the same two-pointer loop.
- “Can you do it without a regular expression?” Yes: check the character
codes (
'a'to'z','A'to'Z','0'to'9') yourself.
Related problems:
- Two Sum II (next problem): the same “one pointer at each end” idea, but the pointers move based on a sum.
- Container With Most Water (week 2): two pointers from both ends, choosing which one to move.
- The week 2 overview has the general template for converging two pointers.