A palindrome, ignoring punctuation and case
Given a string s, return true if it reads the same forwards and backwards
once you keep only its letters and digits and ignore the difference between upper and lower case. Otherwise return
false. The string contains printable ASCII characters only.
Examples
| Input | Output | Why |
|---|---|---|
s = "Was it a car or a cat I saw?" | true | Letters only: wasitacaroracatisaw, the same reversed. |
s = "race a car" | false | raceacar reversed is racaecar. |
s = " .," | true | Nothing is left to compare, and an empty string is a palindrome. |
Constraints
- 0 ≤ s.length ≤ 2 × 10⁵
- s consists of printable ASCII characters
Hints
Hint 1
Building a cleaned, lower-cased copy and comparing it with its reverse works, in O(n) extra memory. Can you compare in place?
Hint 2
Put one pointer at each end. If either points at a character that does not count, move it inward and look again.
Hint 3
When both point at letters or digits, compare them case-insensitively. A mismatch ends the search; a match moves both inward.
Where people lose marks
- Skipping in an inner while loop without re-checking i < j, which can run a pointer past the other or off the end of a string of punctuation.
- Comparing without lower-casing, so "No lemon" fails on N against n.
- Treating digits as characters to skip. "0P" is not a palindrome: 0 and p differ.
Dry run on "No, Don!"
Read it one frame at a time, the way you would trace the code on paper in an interview. Each frame shows the state after the step it describes.
-
Step 1 / 7sN0io1,2␣3D4o5n6!7ji0j7
i at the left end, j at the right end.
-
Step 2 / 7sN0io1,2␣3D4o5n6!7ji0j7
"!" does not count: skip it, j = 6.
-
Step 3 / 7sN0io1,2␣3D4o5n6j!7i0j6
N and n match ignoring case. Move both inward.
-
Step 4 / 7sN0o1i,2␣3D4o5jn6!7i1j5
o and o match ignoring case. Move both inward.
-
Step 5 / 7sN0o1,2i␣3D4jo5n6!7i2j4
"," is not a letter or digit: skip it, i = 3.
-
Step 6 / 7sN0o1,2␣3iD4jo5n6!7i3j4
"␣" is not a letter or digit: skip it, i = 4.
-
Step 7 / 7sN0o1,2␣3D4i/jo5n6!7resulttrue
The pointers have met and every pair matched: a palindrome.
How to think about it
A palindrome check compares the first character with the last, the second with the second-last, and so
on. Here some characters do not count, so the two pointers i (from the left) and j
(from the right) each skip over them independently:
- If
s[i]is not a letter or digit, moveiright. - Otherwise, if
s[j]is not, movejleft. - Otherwise compare them in lower case. Different: return false. Equal: move both inward.
The loop stops when the pointers meet or cross; every pair that counted has matched, so return true. Each step moves at least one pointer, so the loop runs at most n times.
Complexity. Time O(n) · Space O(1)
The solution, in six languages
Each one is compiled and run against the test table before it is published. Java is reviewed by hand.
def is_palindrome(s):
i, j = 0, len(s) - 1
while i < j:
if not s[i].isalnum():
i += 1
elif not s[j].isalnum():
j -= 1
elif s[i].lower() != s[j].lower():
return False
else:
i += 1
j -= 1
return True#include <string>
#include <cctype>
bool solve(const std::string& s) {
int i = 0, j = (int)s.size() - 1;
while (i < j) {
unsigned char a = s[i], b = s[j];
if (!std::isalnum(a)) ++i;
else if (!std::isalnum(b)) --j;
else if (std::tolower(a) != std::tolower(b)) return false;
else { ++i; --j; }
}
return true;
}class Solution {
public boolean isPalindrome(String s) {
int i = 0, j = s.length() - 1;
while (i < j) {
char a = s.charAt(i), b = s.charAt(j);
if (!Character.isLetterOrDigit(a)) i++;
else if (!Character.isLetterOrDigit(b)) j--;
else if (Character.toLowerCase(a) != Character.toLowerCase(b)) return false;
else { i++; j--; }
}
return true;
}
}function isPalindrome(s) {
const counts = c => /[a-z0-9]/i.test(c);
let i = 0, j = s.length - 1;
while (i < j) {
if (!counts(s[i])) i++;
else if (!counts(s[j])) j--;
else if (s[i].toLowerCase() !== s[j].toLowerCase()) return false;
else { i++; j--; }
}
return true;
}fn solve(s: &str) -> bool {
let b = s.as_bytes();
if b.is_empty() { return true; }
let (mut i, mut j) = (0usize, b.len() - 1);
while i < j {
if !b[i].is_ascii_alphanumeric() { i += 1; }
else if !b[j].is_ascii_alphanumeric() { j -= 1; }
else if b[i].to_ascii_lowercase() != b[j].to_ascii_lowercase() { return false; }
else { i += 1; j -= 1; }
}
true
}import Data.Array
import Data.Char (isAlphaNum, toLower)
solve :: String -> Bool
solve s = go 0 (n - 1)
where
n = length s
a = listArray (0, n - 1) s
go i j
| i >= j = True
| not (isAlphaNum (a ! i)) = go (i + 1) j
| not (isAlphaNum (a ! j)) = go i (j - 1)
| toLower (a ! i) /= toLower (a ! j) = False
| otherwise = go (i + 1) (j - 1)Variants to try
- Allow deleting at most one character to make it a palindrome: on the first mismatch, try skipping either side once.
- Unicode letters: case folding is no longer one character to one character, and the cleaned copy becomes the safer approach.
Next problems
Merge two sorted arrays
The step at the heart of merge sort: one pointer per array, and the smaller front value goes next.
Open the problem → Easy10 minMove the zeros to the end
One pointer reads every element, the other marks where the next non-zero belongs. The order of the non-zero values is kept.
Open the problem → Easy10 minPair with a given sum in a sorted array
The cleanest example of the two-pointer idea: sorted input, one pass, no extra memory.
Open the problem →Write a solution and run it against the real test table.
Keep going
Merge two sorted arrays
The step at the heart of merge sort: one pointer per array, and the smaller front value goes next.
Open the problem → Easy10 minMove the zeros to the end
One pointer reads every element, the other marks where the next non-zero belongs. The order of the non-zero values is kept.
Open the problem → Easy10 minPair with a given sum in a sorted array
The cleanest example of the two-pointer idea: sorted input, one pass, no extra memory.
Open the problem → Two pointersThe pattern behind it
Two indices walking a sorted or paired structure, each step ruling out one candidate for good.
Read the pattern →Preparing for a real process? Quant interview preparation, or book a free 20-minute call.