Algorithm

Valid Palindrome

Two Pointer Pattern

Valid Palindrome

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⁵
  • s consists of printable ASCII characters
  • Ignore all non-alphanumeric characters
  • Comparison is case-insensitive
EXAMPLE 1
Input: s = "A man, a plan, a canal: Panama"
Output: true
Keeping only letters and digits and lowercasing gives "amanaplanacanalpanama", which reads the same in both directions.
EXAMPLE 2
Input: s = "race a car"
Output: false
The kept characters are "raceacar". Reading inward from both ends, the fourth pair disagrees (e against a), so it is not a mirror.
EXAMPLE 3
Input: s = " "
Output: true
The only character is a space, which is ignored. Nothing is left to compare, so it counts as a palindrome.
EXAMPLE 4
Input: s = "0P"
Output: false
Both a digit and a letter are kept: "0p". The first and last characters differ, so it is not a palindrome.
Which characters actually get compared?
Only letters (a–z, A–Z) and digits (0–9). Every space, punctuation mark, and symbol is ignored completely.
Does capitalization matter?
No — the comparison is case-insensitive, so 'A' and 'a' count as the same character.
What should an empty string, or one with no letters or digits, return?
True. Once the ignored characters are removed there is nothing left that could mismatch, so it counts as a palindrome by convention.
Do I return the cleaned string, or just a yes/no?
Just a boolean — true if it reads the same both ways, false otherwise.

We want to determine if a given phrase reads the exact same forward and backward. However, real-world text is full of "noise" like spaces, punctuation, symbols, and varying capitalizations. To find the underlying symmetry, we must ignore all non-alphanumeric characters and treat uppercase and lowercase letters as identical. How can we check for this symmetry efficiently?

The Filtering Tax

The most straightforward approach is to filter out the noise first. We create a brand new string, copying over only the alphanumeric characters in their lowercase forms. Once we have this clean string, we compare it to a fully reversed copy of itself. If they are identical, the phrase is a palindrome.

While this runs in linear time, it forces us to allocate memory for a whole new cleaned string and its reverse. If the input string is very large, this O(N) extra space is a wasteful memory overhead.

python
# Filter and lowercase
cleaned = [char.lower() for char in s if char.isalnum()]
cleaned_str = "".join(cleaned)

# Compare with reverse
return cleaned_str == cleaned_str[::-1]
The Inward Pointers

To eliminate the memory overhead entirely, we can verify the symmetry in-place using two converging pointers:
- The Left Explorer (left): Starts at the very beginning of the string and marches inward to the right.
- The Right Explorer (right): Starts at the very end of the string and marches inward to the left.

By skipping noise on the fly, we don't need to copy any characters.

Symmetrical Convergence

The two pointers step inward toward each other. If a pointer lands on a non-alphanumeric character (like a space or comma), it simply skips past it. Once both pointers are resting on valid alphanumeric characters, we compare them case-insensitively.

If they match, we continue our inward march. If they mismatch at any point, we can early-exit and return false immediately, saving unnecessary work. If the pointers meet or cross in the center without any mismatch, the symmetry is fully verified.

python
left = 0
right = len(s) - 1

while left < right:
    # Skip noise from the left
    if not s[left].isalnum():
        left += 1
    # Skip noise from the right
    elif not s[right].isalnum():
        right -= 1
    else:
        # Compare alphanumeric characters case-insensitively
        if s[left].lower() != s[right].lower():
            return False
        left += 1
        right -= 1

return True
Worked Example:Symmetry Scan
0
A
left
1
,
2
3
b
4
,
5
6
a
right
We place 'left' at index 0 and 'right' at index 6. Both 'A' and 'a' are alphanumeric and match case-insensitively.
0
A
1
,
2
3
b
left
4
,
5
right
6
a
left advances to 3 ('b'). right is at index 5 (' '), which is not alphanumeric, so right skips it to index 4 (',').
0
A
1
,
2
3
b
leftright
4
,
5
6
a
right skips the comma at index 4 and lands on 'b' at index 3. The pointers meet, verifying that the phrase is a palindrome.
Interactive Strategy Visualization

Valid Palindrome Visualization

Checking symmetry while ignoring symbols

L
M
0
a
1
d
2
a
3
m
4
,
5
6
i
7
n
8
9
E
10
d
11
e
12
n
13
,
14
15
I
16
'
17
m
18
19
A
20
d
21
a
22
R
m
23
CURRENT STEP
Start pointers at both ends.

Key Insight

We can skip non-alphanumeric characters by iterating the pointers past them before performing the comparison.

Pointers Strategy

Converge from both ends. If characters (lower-cased) don't match, return false immediately. If they meet, return true.

O(N) Time · O(N) Space Clean & Reverse
→
O(N) Time · O(1) Space Converging Scan