Valid Palindrome Solution

Problem

Determine whether a string is a palindrome after removing all non-alphanumeric characters and converting to lowercase. Spaces, punctuation, and symbols are all ignored — only letters and digits count.

Input: "A man, a plan, a canal: Panama"
Output: true
Explanation: stripping non-alphanumeric characters gives "amanaplanacanalpanama", which reads the same forwards and backwards.

Counter-example:

Input: "race a car"
Output: false
Explanation: stripping gives "raceacar", which is not a palindrome.

Intuition

After filtering to only letters and digits and lowercasing everything, the problem is just: does this sequence read the same from both ends? That framing immediately suggests two pointers — one starting at the left, one at the right — marching inward and comparing characters. Any non-alphanumeric character can be skipped on the fly, so we never need to build a cleaned copy of the string at all.

Approach 1 — Clean String

Build a filtered lowercase copy of the string, then check whether it equals its own reverse. Simple and easy to read.

Iterate over every character in the string.
If the character is alphanumeric, append its lowercase version to a result list.
Compare the list to itself reversed.

1def isPalindrome(s: str) -> bool:
2    cleaned = [char.lower() for char in s if char.isalnum()]
3    return cleaned == cleaned[::-1]

Time: O(n) — one pass to build the cleaned string, one pass to compare.
Space: O(n) — the cleaned string can be as large as the input.

Approach 2 — Two Pointers In Place

Use two pointers that meet in the middle without allocating any extra string. Each pointer skips over non-alphanumeric characters independently, then compares the characters they land on.

Place a left pointer at index 0 and a right pointer at the last index.
Advance left forward past any non-alphanumeric characters.
Advance right backward past any non-alphanumeric characters.
Compare the characters at left and right case-insensitively; if they differ, return false.
Move both pointers one step inward and repeat until they cross.
If all comparisons matched, return true.

1def isPalindrome(s: str) -> bool:
2    left, right = 0, len(s) - 1
3    while left < right:
4        while left < right and not s[left].isalnum():
5            left += 1                      # skip non-alphanumeric from the left
6        while left < right and not s[right].isalnum():
7            right -= 1                     # skip non-alphanumeric from the right
8        if s[left].lower() != s[right].lower():
9            return False
10        left += 1
11        right -= 1
12    return True

Time: O(n) — each character is visited at most once by either pointer.
Space: O(1) — only two integer indices; no extra allocation.

Complexity Summary

Approach	Time	Space	When to use
Clean String	O(n)	O(n)	Readability is the priority and space isn't a concern
Two Pointers	O(n)	O(1)	Memory is constrained or you want the canonical interview answer

Common Mistakes

Forgetting to skip non-alphanumeric chars in the inner loops: if you only skip them before the outer loop starts, a trailing punctuation character like the : in "Panama:" will cause a wrong mismatch.
Comparing characters before lowercasing: 'A' != 'a' in a raw char comparison even though they should be treated as equal.
Returning false on an empty or all-punctuation string: after filtering, an empty sequence is a valid palindrome — both approaches naturally return true in this case because the while condition left < right is never true.
Off-by-one when the pointers meet: the loop condition left < right (not <=) is intentional — when both pointers land on the same character, there's nothing to compare against.
Building a new string in the two-pointer approach: the whole point of Approach 2 is to avoid that allocation — resist the urge to call .strip() or equivalent before entering the loop.

Valid Palindrome — Solution