Valid Palindrome
Understanding the Problem
This is more than a plain "is this string a palindrome?" check. The problem adds two preprocessing rules: ignore case and ignore non-alphanumeric characters. The string "A man, a plan, a canal: Panama" has spaces, commas, and a colon, but after removing those characters and lowercasing the rest, it becomes "amanaplanacanalpanama", which reads the same forwards and backwards.
The two approaches below differ on one decision: whether to build the cleaned-up string explicitly, or skip the ignored characters while comparing.
Key Constraints:
1 <= s.length <= 2 * 10^5→ With up to 200,000 characters, the solution needs to run in O(n) time. Both approaches do; they differ in space usage.sconsists only of printable ASCII characters → The input can contain letters, digits, spaces, punctuation, and symbols, but no Unicode characters. This means a single byte per character and a fixed test for "alphanumeric".
Approach 1: Filter and Reverse
Intuition
Do exactly what the problem describes: remove everything that isn't a letter or digit, convert the rest to lowercase, and check whether the result is a palindrome.
To check whether a string is a palindrome, compare it against its reverse. If the cleaned string equals its reverse, it is 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 allocates a cleaned string and a reversed copy, both up to n characters. The next approach removes those allocations by comparing characters directly on the original string from both ends.
Approach 2: Two Pointers (Optimal)
Intuition
Work directly on the original string instead of building a cleaned copy. Place one pointer at the start and one at the end. Move them toward each other, skipping any character that isn't alphanumeric. When both pointers rest on alphanumeric characters, compare them case-insensitively. If they ever differ, the string is not a palindrome. If the pointers cross without a mismatch, it is.
This does the filtering and comparison in a single pass, with no extra string allocated.
A palindrome reads the same from both ends, so the i-th alphanumeric character from the front must equal the i-th from the back. The two pointers enumerate exactly those alphanumeric characters in that paired order: skipping ignored characters means each comparison lines up the next front character with the next back character. The sequence of pairs compared is identical to comparing the cleaned string from Approach 1 against its reverse, so the two approaches accept and reject the same strings.
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.