125. Valid Palindrome
easyDecide whether a string is a palindrome after removing non-alphanumeric characters and lowercasing. Classic two-pointer warm-up with a character-cleanup twist.
By Sam K., Founder, InterviewChamp.AI · Last verified
Problem
A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers. Given a string s, return true if it is a palindrome, or false otherwise.
Constraints
1 <= s.length <= 2 * 10^5s consists only of printable ASCII characters.
Examples
Example 1
s = "A man, a plan, a canal: Panama"trueExplanation: After cleaning: "amanaplanacanalpanama" — palindrome.
Example 2
s = "race a car"falseExplanation: After cleaning: "raceacar" — not a palindrome.
Example 3
s = " "trueSolve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
Hints
Progressive — try the first before opening the next.
Hint 1
Cleaning the string first (filter + lowercase) into a new string then comparing it to its reverse works — O(n) time, O(n) extra space.
Hint 2
Can you skip the copy and compare in place?
Hint 3
Two pointers from the ends. Skip past any non-alphanumeric character on either side. When both point at a valid character, compare lowercase. Mismatch = false; equal = advance both.
Solution approach
Reveal approach
Two-pointer in-place comparison. Left starts at 0, right at length-1. In a loop: advance left past any non-alphanumeric character; retreat right past any non-alphanumeric character. If left has crossed right, return true. Otherwise compare lowercase characters at the two positions — mismatch returns false, equal advances both pointers. O(n) time, O(1) extra space. Avoids the allocation a 'clean then compare' approach would need.
Complexity
- Time
- O(n)
- Space
- O(1)
Related patterns
- two-pointers
Related problems
Asked at
Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).
- Meta
- Amazon
- Microsoft
More Strings practice problems
- 3. Longest Substring Without Repeating Characters
- 5. Longest Palindromic Substring
- 6. Zigzag Conversion
- 14. Longest Common Prefix
- 20. Valid Parentheses
- 28. Find the Index of the First Occurrence in a String
- 49. Group Anagrams
- 58. Length of Last Word