LeetCode · #125

Valid Palindrome Solution

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

Section One · Problem

Problem Statement

🏷️

Difficulty

Easy

🔗

LeetCode

Problem #125

🏗️

Pattern

Two Pointers — converge from ends

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

Example 1

 Input: s = "A man, a plan, a canal: Panama" Output: true // After cleanup: "amanaplanacanalpanama" — reads same both ways 

Example 2

 Input: s = "race a car" Output: false // After cleanup: "raceacar" — not a palindrome 

Constraints

• 1 ≤ s.length ≤ 2 × 10⁵ • s consists of printable ASCII characters

Section Two · Approach 1

Brute Force — Build Clean String O(n)

Filter out non-alphanumeric characters, convert to lowercase, then check if the cleaned string equals its reverse. Simple but uses O(n) extra space for the cleaned copy.

Why we can do better

Problem: Building a new string and its reverse requires O(n) extra memory. Two pointers can compare characters in-place from both ends, skipping non-alphanumeric characters on the fly — achieving O(1) space.

Java — Clean + Reverse

 class Solution {
public boolean isPalindrome(String s) {
StringBuilder clean = new StringBuilder();
for (char c : s.toCharArray())
if (Character.isLetterOrDigit(c))
                clean.append(Character.toLowerCase(c));
return clean.toString().equals(clean.reverse().toString());
    }
}

Python — Clean + Reverse

 class Solution:
def isPalindrome(self, s: str) -> bool:
        clean = [c.lower() for c in s if c.isalnum()]
return clean == clean[::-1]

Metric	Value
Time	O(n) — one pass to clean, one to reverse
Space	O(n) — cleaned string + reversed copy

Section Three · Approach 2

Two Pointers — O(n) time, O(1) space

Place one pointer at the start and one at the end. Move them inward, skipping non-alphanumeric characters. At each step, compare the two characters (case-insensitive). If they ever differ, return false. If the pointers cross, it's a palindrome.

💡 Mental model: Two people hold opposite ends of a banner. They each walk inward, ignoring decorations (non-letters). At each step they compare their current letter — if every pair matches, the banner reads the same from both sides.

Algorithm

Step 1: Set left = 0, right = s.length() - 1.
Step 2: While left < right: skip non-alphanumeric chars by advancing left / retreating right.
Step 3: Compare toLowerCase(s[left]) with toLowerCase(s[right]). If different → false.
Step 4: Move both pointers inward: left++, right--.
Step 5: If pointers cross without mismatch → true.

🎯 When to recognize this pattern:

Any problem comparing elements from both ends of a sequence — palindrome checks, container problems, sorted-array pair finding.
The signal is symmetry: if the answer depends on matching the first with the last, second with second-to-last, etc., use converging two pointers.

Section Four · Trace

Visual Walkthrough

Trace through s = "A man, a plan, a canal: Panama":

Two Pointers — converge from both ends, skip non-alphanumeric

Section Five · Implementation

Code — Java & Python

Java — Two Pointers

 class Solution {
public boolean isPalindrome(String s) {
int left = 0, right = s.length() - 1;
while (left < right) {
while (left < right && !Character.isLetterOrDigit(s.charAt(left)))
                left++; // skip non-alphanumeric while (left < right && !Character.isLetterOrDigit(s.charAt(right)))
                right--; // skip non-alphanumeric if (Character.toLowerCase(s.charAt(left)) !=
Character.toLowerCase(s.charAt(right)))
return false; // mismatch
left++;
            right--;
        }
return true;
    }
}

Python — Two Pointers

 class Solution:
def isPalindrome(self, s: str) -> bool:
        left, right = 0, len(s) - 1 while left < right:
while left < right and not s[left].isalnum():
                left += 1 while left < right and not s[right].isalnum():
                right -= 1 if s[left].lower() != s[right].lower():
return False
left += 1
right -= 1 return True 

Section Six · Analysis

Complexity Analysis

Approach	Time	Space	Trade-off
Clean + Reverse	O(n)	O(n)	Simple but builds two extra strings
Two Pointers ← optimal	O(n)	O(1)	In-place comparison, no extra strings

Section Seven · Edge Cases

Edge Cases & Pitfalls

Case	Input	Why It Matters
Empty after cleanup	`" "` or `",.!"`	All non-alphanumeric → empty string is a palindrome → true.
Single character	`"a"`	Trivially a palindrome.
Mixed case	`"Aa"`	Must compare case-insensitively → true.
Numbers in string	`"0P"`	'0' and 'P' are both alphanumeric. '0' ≠ 'p' → false.
All same character	`"aaaa"`	Every pair matches → true.

⚠ Common Mistake: Forgetting the left < right guard inside the inner while-loops that skip non-alphanumeric characters. Without it, pointers can overshoot each other and cause an IndexOutOfBoundsException on strings like ".,,".

← Back to Two Pointers problems

LearningTree

LC 125 · Valid Palindrome — Solution & Explanation | DSA Guide