Valid Palindrome (LC 125)

Pattern: Two Pointers (Skip Non-Alphanumeric) Difficulty: Easy Key Concept: One pointer from each end. Skip non-alphanumerics. Compare lowercased characters.

Problem Statement

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

Given a string s, return true if it is a palindrome, else false.

Example

• s = "A man, a plan, a canal: Panama" → true
• s = "race a car" → false
• s = " " → true (empty after cleaning)

---

1. Algorithm & Pseudocode

Build cleaned string then compare

clean = s where each char is lowercase, alphanumeric only
return clean.equals(clean.reverse())

Easy to read but uses O(n) extra space.

Optimal — Two pointers in place

l = 0, r = s.length() - 1
while l < r:
    while l < r and !alphanumeric(s[l]): l++
    while l < r and !alphanumeric(s[r]): r--
    if lower(s[l]) != lower(s[r]): return false
    l++; r--
return true

---

2. Step-by-Step Analysis

Why two pointers A palindrome means symmetric around the center. Comparing s[l] with s[r] for l = 0..n/2 is enough — we never need to revisit.

Why inner while-loops for skipping Non-alphanumerics (spaces, punctuation) are ignored by the problem. Inside the outer loop, advance l or retreat r until both point at alphanumeric chars.

Why Character.toLowerCase Comparison ignores case. Character.isLetterOrDigit already includes digits, so "0P" flagged digits and letters correctly.

Edge cases

• Empty / whitespace-only → l and r cross immediately → returns true (vacuously a palindrome).
• Single alphanumeric "a." → after skipping, l == r, loop ends → true.

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

l=0  s[l]='A'  r=29 s[r]='a'   lower a == a ✓
l=1  s[l]=' '  skip → l=2 'm'  r=28 'm'  ✓
l=3  s[l]='a'  r=27 'a'         ✓
... (continues)

---

3. The Dry Run

s = "0P"

Step	l	r	s[l]	s[r]	After lower compare	Result
1	0	1	‘0’	‘P’	‘0’ != ‘p’	false

s = "race a car"

After cleaning conceptually: "raceacar". The 3rd char from the left is c, from the right is a → mismatch → false.

s = " "

l=0, r=0 → loop body doesn’t execute → true.

---

4. Java Solution

Helper-string Brute Force

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

Time: (O(n)) Space: (O(n))

Optimal

class Solution {
    public boolean isPalindrome(String s) {
        int l = 0, r = s.length() - 1;
        while (l < r) {
            while (l < r && !Character.isLetterOrDigit(s.charAt(l))) l++;
            while (l < r && !Character.isLetterOrDigit(s.charAt(r))) r--;
            if (Character.toLowerCase(s.charAt(l)) != Character.toLowerCase(s.charAt(r))) return false;
            l++; r--;
        }
        return true;
    }
}

Time: (O(n)) Space: (O(1))

---

5. The “Java vs. Others” Edge

• Character.isLetterOrDigit(c) follows Unicode rules — for ASCII-only tests, manual check is slightly faster but rarely matters.
• Character.toLowerCase handles non-ASCII letters too — use it for safety.
• The two-pointer version is strictly better: same time, 1/n the memory.

---

6. Complexity Summary

Approach	Time	Space	Notes
Cleaned string	(O(n))	(O(n))	Easy to read, extra allocation
Two Pointers	(O(n))	(O(1))	Canonical answer