Valid Palindrome

Explanation & Solution

Description

Given a string s, return true if it is a palindrome after converting all uppercase letters to lowercase and removing all non-alphanumeric characters.

A string is a palindrome if it reads the same forward and backward.

Input: s = "Madam, I'm Adam"

Output: true

Explanation: After removing non-alphanumeric characters and converting to lowercase, the string becomes "madamimadam", which is a palindrome.

Constraints

1 <= s.length <= 2 * 10⁵
s consists only of printable ASCII characters.

Approach

Two Pointers pattern

1. Initialize Two Pointers

Set left to 0 (start of string)
Set right to s.length - 1 (end of string)
These pointers will move toward each other

2. Skip Non-Alphanumeric Characters

Advance left forward while the character at left is not alphanumeric
Advance right backward while the character at right is not alphanumeric
This effectively ignores spaces, punctuation, and special characters

3. Compare Characters

Convert both s[left] and s[right] to lowercase
If they are not equal, return false immediately
The string cannot be a palindrome if any mirrored pair differs

4. Move Pointers Inward

Increment left by 1
Decrement right by 1
Repeat from step 2 until left >= right

5. Return True

If the loop completes without finding a mismatch, the string is a valid palindrome
Return true

Key Insight

The two-pointer approach avoids creating a new filtered string, saving memory
By skipping non-alphanumeric characters in-place and comparing case-insensitively, we check palindrome validity in a single pass

Time

O(n)each character is visited at most once

Space

O(1)only two pointer variables are used

Visualization

Input:

[M, a, d, a, m, ,, , I, ', m, , A, d, a, m]

—

Press ▶ or use ← → to step through

Left (L)Right (R)ConvergedDone

7 steps

Solution Code

Two Sum II - Input Array Is Sorted

Remove Duplicates from Sorted Array