Valid Palindrome
The key idea
Walk one pointer in from each end. Skip any character that is not a letter or digit, compare the rest case-insensitively, and they must match in mirror order. This checks the palindrome in place without building a cleaned copy of the string.
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^5sconsists only of printable ASCII characters.
Examples
Input: s = "A man, a plan, a canal: Panama"
Output: true
Input: s = "race a car"
Output: false
Input: s = " "
Output: true
Complexity
Time: O(n) Space: O(1)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More Two Pointers problems
- 3SumMEDIUM
- 4SumMEDIUM
- Concatenation of ArrayEASY
- Container With Most WaterMEDIUM
- Is SubsequenceEASY
- Merge Sorted ArrayEASY
- Merge Strings AlternatelyEASY
- Move ZeroesEASY
- Next PermutationMEDIUM
- Remove Duplicates from Sorted ArrayEASY
- Remove Duplicates from Sorted Array IIMEDIUM
- Remove ElementEASY