Difficulty: Easy Pattern: Two Pointers LeetCode: https://leetcode.com/problems/valid-palindrome/
s.charAt(i) reading slot i. glossaryGiven a string s, return true if it is a palindrome considering only
alphanumeric characters and ignoring case, otherwise false. An empty string
counts as a palindrome.
Signature:
boolean isPalindrome(String s)
Examples (verbatim from LeetCode):
Input: s = "A man, a plan, a canal: Panama"
Output: true
Input: s = "race a car"
Output: false
Input: s = " "
Output: true
A palindrome is a word that reads the same forwards and backwards – “racecar”,
“mom”, “noon”. How would you check by eye? Put one finger on the first letter and
one on the last; if they match, slide both fingers one step inward; keep going.
If every finger-pair agrees before the fingers meet in the middle, it’s a
palindrome. This finger trick is two pointers:
one index (left) at the start, one (right) at the end, moving toward each other.
Let’s watch it on the tiniest real case, s = "mom":
left=0 points at 'm', right=2 points at 'm' -> match, move both inward.left=1, right=1 -> the fingers have met in the middle, so stop. No mismatch
was ever found, so it’s a palindrome.This problem adds two twists. First, the string is full of spaces and punctuation
(',', ':', ' ') that we must ignore – a comma should never count as a
mismatch. Second, uppercase and lowercase count as the same ('A' equals 'a').
The word for “a letter or a digit” is alphanumeric – so 'a' and '7' count,
but ' ' and ',' do not.
Here is the general rule with the skipping built in. At each step, if the
character under a finger is not alphanumeric, slide just that finger past it and
do not compare yet. Once both fingers sit on real letters or digits, lowercase
them and compare. If they differ, return false immediately. If they match, move
both inward. When the fingers meet or cross with no mismatch, every relevant pair
has agreed, so return true. Sweeping through the string once this way is a
linear scan; because both fingers only
ever move forward, the whole check finishes in O(n) time.
Pause and pick before expanding. A wrong first guess teaches more than a fast right one.
Q1 (recall). This problem must ignore some characters before comparing. Which set does it keep (the “alphanumeric” ones)?
Q2 (comprehend). Trace s = "Aa" (length 2). Both characters are alphanumeric. What is the result, and why?
false – ‘A’ and ‘a’ are different characterstrue – after lowercasing both are ‘a’, they match, then the pointers cross and the loop exitsfunction isPalindrome(s):
set left to first index of s
set right to last index of s
while left < right:
if character at left is not alphanumeric:
advance left
continue
if character at right is not alphanumeric:
move right back one
continue
if lowercase(left char) is not equal to lowercase(right char):
return false
advance left
move right back one
return true
class Solution {
public boolean isPalindrome(String s) {
int left = 0, right = s.length() - 1;
while (left < right) {
char l = s.charAt(left);
char r = s.charAt(right);
if (!Character.isLetterOrDigit(l)) {
left++;
continue;
}
if (!Character.isLetterOrDigit(r)) {
right--;
continue;
}
if (Character.toLowerCase(l) != Character.toLowerCase(r)) {
return false;
}
left++;
right--;
}
return true;
}
}
We snapshot the two characters into l and r first so the two skip-checks
read cleanly. Character.isLetterOrDigit matches the problem’s “alphanumeric”
exactly (it accepts Unicode letters, which LeetCode accepts too). Comparing
after toLowerCase handles the case-insensitive rule. The continue after
advancing one pointer restarts the loop so we re-validate the new character
before comparing — this is what keeps the skip logic simple.
Time: O(n) -- each character is visited at most once as left or right advance.
Space: O(1) -- only two index variables are used; no copy of the string.
Step-by-step on s = "A man, a plan, a canal: Panama" (length 25, indices 0..24).
We show left, right, the characters considered, and the action. M(0) means
“match at this step”, SKIP means a character was ignored.
| Step | left | right | left char | right char | Action |
|---|---|---|---|---|---|
| 1 | 0 | 24 | ‘A’ | ‘a’ (last) | match -> left++, right– |
| 2 | 1 | 23 | ’ ‘ | ‘m’ | SKIP left (space) -> left++ |
| 3 | 2 | 23 | ‘m’ | ‘m’ | match -> left++, right– |
| 4 | 3 | 22 | ‘a’ | ‘a’ | match -> left++, right– |
| 5 | 4 | 21 | ‘n’ | ‘m’ | match? ‘n’ vs ‘a’… |
(A full trace is 13 matches; the key point is that every compared pair is equal
and the pointers cross without finding a mismatch, so the function returns
true.) The loop exits when left >= right, at which point every relevant pair
has been verified.
Q1 (apply). Trace s = "ab". What is returned?
truefalse, because ‘a’ does not equal ‘b’Q2 (analyze). What happens if a skip branch advances its pointer but you forget the continue (or forget the left++ / right--)?
Q3 (transfer). Suppose the task changed to: “return true if the string can be a palindrome after deleting at most one character.” How would you adapt the approach?
== on Character objects. Comparing boxed Characters with ==
breaks for values outside the cached range; always compare char primitives
(as above) or use .equals.'A' != 'a', so a mixed-case palindrome
like "Aa" would wrongly return false.Character.isLetter alone would drop them and break inputs like "0P".continue without left++), the loop never progresses.