Valid Palindrome: definition
A palindrome reads the same forward and backward. For this task, keep letters and digits and ignore letter case, spaces, and punctuation.
Task example: Valid Palindrome
Return True if the string is a palindrome after ignoring non-alphanumeric characters and letter case; otherwise return False. Digits count. An empty cleaned string is a palindrome.
The demos use printable ASCII characters, matching the problem constraints.
Reverse & compare: video explanation
s = "Race car!" → True
Prefer reading? Follow the steps below.
- Read the string from left to right. Keep each letter or digit, convert it to lowercase, and append it to a list. Skip spaces and punctuation.
- Join the list into one string, then reverse it. Compare the cleaned string with its reverse. Equal means True; different means False.
- Race car! becomes racecar. Its reverse is also racecar, so the result is True.
Time complexity · O(n)
Filtering, joining, reversing, and comparing each take O(n) time. A fixed number of linear passes is still O(n).
Space complexity · O(n)
The list, cleaned string, and reversed copy grow with the input, so extra space is O(n).
Two pointers: video explanation
s = "Race car!" → True
Prefer reading? Follow the steps below.
- Start left at the first character and right at the last. While left is before right, inspect the remaining range.
- Skip any non-alphanumeric character by moving its pointer inward. Compare the lowercase letters or digits at both ends.
- If they differ, return False immediately. If they match, move both pointers inward. Return True when the pointers meet or cross.
- For Race car!, skip !, then match R with r, a with a, and c with c. Skip the space. The pointers meet at e: return True.
Why it works: matching outer characters leave only the inside to check. Compared with reverse & compare, time stays O(n), but extra space improves from O(n) to O(1). Never sort the string: its order matters.
Time complexity · O(n)
Both pointers only move inward. Together they visit at most n positions, so the worst-case time is O(n).
Space complexity · O(1)
Only two indices and individual characters are stored. No cleaned or reversed copy is created: O(1) extra space.