The problem
A phrase is a palindrome if it reads the same forwards and backwards after you drop every character that is not a letter or digit and ignore upper/lower case. Decide whether the given phrase is one.
Input: "No x in Nixon!" Output: true (cleaned: "noxinnixon")
Picture it
Picture two people reading a shop sign, one starting at the left end and one at the right. They skip spaces and punctuation and don’t care about capitals. Each compares their letter with the other’s and both take one step toward the middle. If any pair disagrees, it’s not a palindrome; if they meet in the middle, it is.
How to recognise it
- You compare a sequence with its own reverse: the first item with the last, the second with the second-to-last.
- That suggests two pointers, one at each end, moving towards each other.
- Some characters must be skipped (anything that is not a letter or digit) and case ignored. A pointer can simply step past a character it should skip.
- Strings can be up to 2 × 10^5 characters, so you want one pass and, ideally, no copies.
Start with brute force
Build the cleaned string (letters and digits only, lower-cased) and compare it with its reverse.
def is_palindrome_brute(s):
clean = [ch.lower() for ch in s if ch.isalnum()]
return clean == clean[::-1]
This is honestly fine for speed: O(n) time. Its cost is memory. It builds a cleaned copy and a reversed copy, each up to 2 × 10^5 characters, so O(n) extra space, and it always reads the whole string even when the first and last characters already differ.
From brute force to the idea
- Find the waste. The reversed copy is only used to compare position i from the front with position i from the back. You can read both directly from the original string.
- Two pointers. Put
lat the start andrat the end. Whilel < r, they point at a pair that must match. - Skip, one step at a time. If
s[l]is not a letter or digit, movelright and try again. Do the same forr, moving left. Each loop round does exactly one thing, which keeps the logic simple. - Compare ignoring case. When both point at letters or digits, compare
s[l].lower()withs[r].lower(). A mismatch means it is not a palindrome, so return at once. - Move inwards. On a match, step both pointers. When they meet or cross, every pair has matched.
This is the key idea: two pointers from both ends, skipping what does not count, with no cleaned copy.
The key idea
Two pointers from both ends, skipping non-letters, compare as you go: O(n) time, no extra copy of the string.
Python solution
def is_palindrome(s):
l, r = 0, len(s) - 1
while l < r:
if not s[l].isalnum():
l += 1
elif not s[r].isalnum():
r -= 1
elif s[l].lower() != s[r].lower():
return False
else:
l, r = l + 1, r - 1
return TrueIn the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.
Complexity
| Approach | Time | Space |
|---|---|---|
| Clean and reverse (brute force) | O(n): one pass to clean, one to reverse, one to compare | O(n): the cleaned and reversed copies |
| Two pointers (shown code) | O(n): each round moves at least one pointer inwards | O(1): two indices |
Edge cases
- Empty string or only spaces and punctuation (
" ",".,"): returnsTrue. The pointers skip everything and meet, and an empty cleaned string counts as a palindrome. - One character: returns
True; the loop never runs. - Digits count (
"0P"): returnsFalse.0is kept, and0is notp. - Underscore is skipped (
"ab_a"): returnsTrue._is not a letter or digit in Python. - Mixed case (
"Aa"): returnsTruethanks to.lower(). - Non-ASCII: Python's
isalnumalso accepts characters such aséand². LeetCode's input is printable ASCII, so this never matters there, but it does for general text.
Common mistakes
- Forgetting
.lower(), so"Aba"returnsFalse. - Building the cleaned string anyway and then running two pointers on it, which keeps the O(n) memory the pointers were meant to save.
- Skipping with an inner
whileloop that does not checkl < r, so on a string of only punctuation the pointer runs off the end and raisesIndexError. - Using
isalphainstead ofisalnum, which drops digits that should be compared.
Given a lowercase string, return True if it can become a palindrome after deleting at most one character. "abca" returns True (delete c or b), and "abc" returns False. Describe your approach, then write it if you like.
Compare with our answer
Run the same two pointers. At the first mismatch, one of the two characters must be the one you delete. Try both: check whether s[l+1..r] or s[l..r-1] is a palindrome. You only get one deletion, so those checks use plain matching with no further skips.
def valid_palindrome_one_delete(s):
def is_pal(l, r):
while l < r:
if s[l] != s[r]:
return False
l, r = l + 1, r - 1
return True
l, r = 0, len(s) - 1
while l < r:
if s[l] != s[r]:
return is_pal(l + 1, r) or is_pal(l, r - 1)
l, r = l + 1, r - 1
return True
"deeee" returns True by deleting the d. Time O(n), because each of the two final checks is one pass. Space O(1).
A strong answer mentions: branching only at the first mismatch, trying both deletions, and why that keeps it O(n) rather than trying every deletion in O(n²).
1. You must reverse only the letters of a string, leaving digits and punctuation exactly where they are. Which approach fits best?
The same skip-and-compare pointers work, with a swap instead of a comparison. A stack of every character also reverses the punctuation, and fixing that afterwards is harder than skipping it.
2. Why does the shown code use O(1) extra space?
No cleaned or reversed copy is ever made. Each step reads s[l] and s[r] and compares single characters. Python strings are immutable, so nothing could be cleaned in place anyway.
3. A learner writes elif s[l] != s[r]: without the .lower() calls. Which input now gets the wrong answer?
A and a are now different, so "Aba" returns False. "race a car" and "0P" were already not palindromes, and "a." only compares the a with itself.
Score 60% or more and the lesson is marked complete.