Valid Palindrome
A phrase is a palindrome if, after you turn every letter into lowercase and remove every character that is not a letter or a digit, it reads the same forwards and backwards.
Given a string s, return true if it is a palindrome, or false otherwise.
Examples
Input s = "A man, a plan, a canal: Panama"
Output true
It becomes "amanaplanacanalpanama".
Input s = "race a car"
Output false
It becomes "raceacar".
Input s = " "
Output true
After removing the space it is empty, and an empty string is a palindrome.
Constraints
- 1 <= s.length <= 200,000
- s contains printable ASCII characters
Stuck? Take one hint at a time
Common mistakes
- Comparing without ignoring case, so "Aa" is wrongly rejected.
- Forgetting to check the pointers stay in range while skipping, which can run off the end on strings like "!!!".
- Cleaning the string and reversing it, which works but uses extra memory.
- Treating underscores or spaces as characters that count.
Questions an interviewer may ask next
- You may delete at most one character. Can the string become a palindrome? (Try both ways at the first mismatch.)
- Return the longest palindromic substring.
- Check a linked list for a palindrome in constant space.
- The input is a stream of characters. What can you check on the fly?
How often this is reported
Commonly reported across 7 of 25 tracked companies
7/25
Grade C: Reported in one source, or backed mainly by volume of reports. This reflects what candidates report, not a guarantee of what any company will ask.
s
"A man, a plan, a canal: Panama"
Expected output
true
Run checks these cases. Submit also runs hidden cases, and shows you the first one that fails.