Valid Palindrome
Last Updated: March 20, 2026
Understanding the Problem
This isn't a straightforward "is this string a palindrome?" check. There are two preprocessing steps baked into the problem: ignore case and ignore non-alphanumeric characters. The string "A man, a plan, a canal: Panama" has spaces, commas, and a colon, but once you strip all of that away and lowercase everything, you get "amanaplanacanalpanama", which reads the same forwards and backwards.
The key question is: do you actually need to build that cleaned-up string, or can you skip over the junk characters on the fly? That distinction is exactly what separates the two approaches below.
Key Constraints:
1 <= s.length <= 2 * 10^5→ With up to 200,000 characters, we need O(n) or better. Both approaches run in O(n) time, but they differ in space usage.sconsists only of printable ASCII characters → We need to handle letters, digits, spaces, punctuation, and symbols. No Unicode edge cases to worry about.
Approach 1: Filter and Reverse
Intuition
The most straightforward approach is to do exactly what the problem says: strip out everything that isn't a letter or digit, convert to lowercase, and then check if the result is a palindrome.
How do you check if a string is a palindrome? Reverse it and see if it matches the original. If the cleaned string equals its reverse, we have a palindrome.
Algorithm
- Iterate through every character in the input string.
- Keep only alphanumeric characters, converting each to lowercase.
- Build a new "cleaned" string from these characters.
- Reverse the cleaned string.
- Compare the cleaned string with its reverse. If they match, return true.
Example Walkthrough
Code
- Time Complexity: O(n). We scan the string once to build the cleaned version, then reverse it, then compare. Three linear passes, so O(n) overall.
- Space Complexity: O(n). We create a new cleaned string that could be up to n characters long, plus another copy for the reversed version.
This approach works but allocates extra strings. What if we compared characters directly from both ends of the original string, skipping non-alphanumeric characters as we go?
Approach 2: Two Pointers (Optimal)
Intuition
Instead of building a cleaned string, we can work directly on the original. Place one pointer at the start and one at the end. Move them toward each other, but skip over any character that isn't alphanumeric. When both pointers land on valid characters, compare them case-insensitively. If they ever mismatch, it's not a palindrome. If the pointers cross without a mismatch, it is.
This avoids allocating any extra strings. We're doing the filtering and comparison in a single pass.
A palindrome is symmetric around its center. If you compare the first valid character with the last valid character, the second with the second-to-last, and so on, you're checking that symmetry directly. By skipping non-alphanumeric characters, you're effectively comparing the same cleaned string that Approach 1 builds, but without ever allocating it.
Each character is visited at most once by each pointer, so the total work is still O(n). But the space drops from O(n) to O(1) since we only use two integer variables.
Algorithm
- Set
leftto 0 andrightto the last index of the string. - While
left < right: - Move
leftforward while it points to a non-alphanumeric character. - Move
rightbackward while it points to a non-alphanumeric character. - If
left >= right, break (all valid characters have been compared). - Compare the lowercase versions of
s[left]ands[right]. - If they don't match, return false.
- Move
leftforward andrightbackward. - Return true.
Example Walkthrough
Code
- Time Complexity: O(n). Each pointer moves from one end to the other, visiting each character at most once. Total work is proportional to the length of the string.
- Space Complexity: O(1). We only use two integer pointers and no additional data structures. The input string is not modified.