125. Valid Palindrome

125

EasyTwo PointersTwo pointers (opposite ends)Converging pointers that skip non-alphanumerics

Valid Palindrome

A phrase is a palindrome if, after converting all uppercase letters to lowercase and removing every character that is not a letter or digit, it reads the same forward and backward. Given a string s, return true if it is a palindrome under those rules, and false otherwise.

Open official problem prompt ↗

In plain English

Decide whether a string is a palindrome once letters are lowercased and all other characters are ignored.

Picture it like this

Two proofreaders start at opposite ends of a sentence and walk toward the middle, silently skipping spaces and punctuation, and only stop to argue when the letters they land on disagree.

Example

Input: s = "A man, a plan, a canal: Panama"
Output: true
Why: Filtered and lowercased, s becomes 'amanaplanacanalpanama', which reads identically in reverse.

Constraints

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

Pattern lesson

See the pattern, then code

Converging pointers that skip non-alphanumerics

↗

Two Pointers

Sorted input, opposite-end scanning, pair search, or in-place compaction.. Walk one pointer in from each end; whenever a pointer lands on a non-alphanumeric character, skip it, and compare only real letters/digits case-insensitively.

New words, made simpleKnow these before the algorithm

Alphanumeric: A character that is a letter or a digit; str.isalnum() tests this.
Converging pointers: Two indices moving toward each other from the two ends of the string.
Case-insensitive: Treating uppercase and lowercase forms of a letter as equal.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Filter then reverse-compare

Clear and correct, but allocates a second string of size n.

Build a cleaned string of lowercased alphanumerics and compare it to its reverse.

Time O(n)Space O(n)

Best choiceIn-place two pointers

No extra allocation and exits early on the first mismatch.

Scan from both ends, skipping non-alphanumerics on the fly and comparing lowercased characters.

Time O(n)Space O(1)

The rule we keep true

Invariant

Every alphanumeric character strictly outside the current [i, j] window has already been matched with its mirror partner.

Why this is correct

Reasoning

Skipping only non-alphanumeric characters means the pointers always align on the k-th real character from each end. Matching those mirrored characters for all k is exactly the definition of a palindrome; the first disagreement proves it is not one, and crossing pointers proves every pair matched.

The algorithm in three movesSay these aloud before coding

1Set i at the start and j at the end

i=0 'A' vs j=end 'a' -> match

2While i < j, advance i past any non-alphanumeric char

skip spaces/commas between comparisons

3Retreat j past any non-alphanumeric char

pointers cross -> return true

4Compare the lowercased characters; return false on mismatch

5Otherwise step both inward; return true if the pointers cross

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

...5

1 · Reads[0]='A', s[last]='a'

2 · AskBoth alphanumeric and equal lowercased?

3 · Update statei=0 j=29

4 · Result'a' == 'a', step inward

Key takeaway

The outer characters 'A' and 'a' match once lowercased; punctuation and spaces are skipped.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 3Place pointers at both ends
i scans forward from the start, j scans backward from the end.
2
Lines 4Loop while pointers have not crossed
Once i meets or passes j, every mirrored pair has been checked.
3
Lines 5-6Skip a left-side non-letter/digit
Advance i without comparing so only real characters are matched.
4
Lines 7-8Skip a right-side non-letter/digit
Retreat j for the same reason on the other end.
5
Lines 9-10Compare mirrored characters
Lowercase both and fail fast on the first mismatch.
6
Lines 11-13Advance both inward
A matching pair is consumed, shrinking the window.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

Empty-after-filtering string such as ',.' returns true
String of a single character
Mixed case like 'Aa'
Strings containing digits, e.g. '0P' returns false

Common beginner mistakes

Forgetting to lowercase before comparing, failing on inputs like 'Aa'
Skipping non-alphanumerics on only one side
Using an if instead of elif so a pointer skips and compares in the same iteration
Treating digits as non-alphanumeric and dropping them

Check your understanding

Why must the skip checks use elif rather than separate if statements before the comparison?

Valid Palindrome

Valid Palindrome

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Two Pointers