Valid Palindrome

Problem in Plain English

Given a string s, decide whether it reads the same forward and backward after converting all letters to lowercase and deleting every non-alphanumeric character. An empty result after cleaning counts as a valid palindrome.

Problem Statement

A phrase is a palindrome when, after converting all uppercase letters to lowercase and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters are letters and digits.

Given a string s, return true if it is a palindrome under these rules, and false otherwise.

Constraints

1 <= s.length <= 2 * 10^5
s consists of printable ASCII characters.

Examples

Example 1

Input: s = "A man, a plan, a canal: Panama"
Output: true

Cleaning leaves "amanaplanacanalpanama", which reads identically in both directions.

Example 2

Input: s = "race a car"
Output: false

Cleaning leaves "raceacar", whose mirror "racaecar" differs, so it is not a palindrome.

Example 3

Input: s = " "
Output: true

Removing the space leaves the empty string, which reads the same forward and backward.

Example 4

Input: s = "0P"
Output: false

Cleaning leaves 0p. Digits are retained, and the digit 0 differs from the letter p, so the result is false.

Example 5

Input: s = "Aa!"
Output: true

The exclamation mark is ignored and uppercase A becomes a, leaving aa, which is a palindrome.

Intuition

Ignore punctuation and spaces, then compare matching positions from opposite ends. For Example 1, the first meaningful character A matches the last a after lowercasing; the next left space is skipped before m matches m. Digits remain meaningful: 0 does not match the letter p. Because the input is printable ASCII, meaningful characters are exactly A-Z, a-z, and 0-9.

Approaches

Reverse and Compare

Solution Details

Reveal Reverse and Compare: intuition, complexity, and code

Intuition

A palindrome equals its own mirror image, so building the cleaned string and testing it against its reversal decides the question. The cleaning pass drops every character the definition ignores.

Step-by-Step Logic

Build a cleaned sequence by reading every character. Retain ASCII letters and digits, convert uppercase letters to lowercase, and skip all other printable ASCII characters.
For Example 1, keep A as a, skip index 1 (a space), keep m, a, and n, then skip the comma at index 5. Continue the same rule through every character.
After the full pass, the cleaned sequence is amanaplanacanalpanama. Build its reversal.
Compare the entire cleaned sequence with its reversal. Return true exactly when they are equal; Example 1 returns true. A cleaned empty sequence also equals its reversal.

Why It Works

The filter retains exactly the characters named by the definition and lowercases every retained letter, so the cleaned sequence represents precisely the meaningful input. A sequence is a palindrome exactly when it equals its reversal: that equality checks every mirror position. The empty sequence and a single retained character satisfy the equality automatically.

Dry Run

Reverse and Compare: variable states at each step
Index	Original character	Action	Cleaned prefix after
0	A	keep as a	a
1	space	skip	a
2	m	keep as m	am
3	a	keep as a	ama
4	n	keep as n	aman
5	,	skip	aman
6	space	skip	aman
7	a	keep as a	amana
8	space	skip	amana
9	p	keep as p	amanap
10	l	keep as l	amanapl
11	a	keep as a	amanapla
12	n	keep as n	amanaplan
13	,	skip	amanaplan
14	space	skip	amanaplan
15	a	keep as a	amanaplana
16	space	skip	amanaplana
17	c	keep as c	amanaplanac
18	a	keep as a	amanaplanaca
19	n	keep as n	amanaplanacan
20	a	keep as a	amanaplanacana
21	l	keep as l	amanaplanacanal
22	:	skip	amanaplanacanal
23	space	skip	amanaplanacanal
24	P	keep as p	amanaplanacanalp
25	a	keep as a	amanaplanacanalpa
26	n	keep as n	amanaplanacanalpan
27	a	keep as a	amanaplanacanalpana
28	m	keep as m	amanaplanacanalpanam
29	a	keep as a	amanaplanacanalpanama
Reverse	none	reversal = amanaplanacanalpanama	amanaplanacanalpanama
Compare	none	full sequences equal; return true	amanaplanacanalpanama

Complexity Analysis

Time Complexity

O(n)

Space Complexity

O(n)

Let n be the original string length and m the number of retained characters. Filtering costs O(n); reversal and equality comparison cost O(m), bounded by O(n). The cleaned sequence and reversal require O(m), bounded by O(n), auxiliary storage. Java also creates an O(n) character array via toCharArray. The ASCII alphabet makes each lowercase operation constant work.

Code

Solution.java

1class Solution {2    public boolean isPalindrome(String s) {3        StringBuilder filtered = new StringBuilder();4        for (char c : s.toCharArray()) {5            if (Character.isLetterOrDigit(c)) {6                filtered.append(Character.toLowerCase(c));7            }8        }9        String cleaned = filtered.toString();10        String reversed = filtered.reverse().toString();11        return cleaned.equals(reversed);12    }13}

Hints

Hint 1

Only letters and digits matter, and casing is ignored, so what should each comparison actually test?

Hint 2

Characters at mirror positions must agree, which suggests checking from both ends toward the middle.

Hint 3

Punctuation can be stepped over during the scan instead of removed beforehand.

Edge Cases

Only spaces or punctuation such as " .,; ", which cleans to the empty string and returns true.
Mixed casing such as "Aa", which matches only when both sides share one case.
Digits mixed with letters such as "0P", where 0 and p correctly fail the comparison.

Common Mistakes and Interview Tips

Skipping non-alphanumeric characters without rechecking left < right inside the skip loops, which overruns on strings like ",.".
Comparing raw characters without lowercasing, so "A" and "a" wrongly mismatch.
Building the cleaned string but forgetting the reversal comparison needs the same case folding.
Treating only letters as meaningful drops digits and wrongly accepts 0P.
Interview tip: state the printable-ASCII assumption. General Unicode can involve different letter categories and case mappings across languages and needs a separate contract.

Key Takeaway

When mirror positions of a sequence must agree, inward pointers test each pair in place with constant extra space.