Valid Palindrome (LC 125)

Pattern: Two Pointers
Difficulty: Easy
Key Concept: Compare characters from both ends while skipping non-alphanumeric characters and ignoring case.

Problem Statement

Given a string s, return true if it is a palindrome when you consider only alphanumeric characters and ignore case.

Input: A string s (may contain letters, digits, spaces, punctuation).
Output: true if the filtered, case-insensitive reading reads the same forwards and backwards; otherwise false.

Examples (conceptual):

"A man, a plan, a canal: Panama" → true
"race a car" → false
" " → true (empty after filtering is often treated as palindrome)

1. Algorithm & Pseudocode

Brute force (filter + reverse + compare)

1. Build a new string (or StringBuilder) with only alphanumeric chars from s, each lowercased.
2. Reverse that string (or compare with a reversed copy).
3. Return whether the string equals its reverse.

Optimal (two pointers on original string)

1. Set left = 0, right = length(s) - 1.
2. While left < right:
   a. While left < right and s[left] is not alphanumeric, left++.
   b. While left < right and s[right] is not alphanumeric, right--.
   c. If lowercase(s[left]) != lowercase(s[right]), return false.
   d. left++, right--.
3. Return true.

2. Step-by-Step Analysis (Beginner-Friendly)

Why ignore non-alphanumeric?
The problem says only letters and digits matter. Spaces and punctuation are “invisible” for the palindrome check.

Why ignore case?
'A' and 'a' should match. Lowercasing (or uppercasing) both sides before comparing keeps the rule simple.

Brute force idea
If you extract only the meaningful characters into a clean string, a palindrome is exactly “reads the same reversed.” This is easy to understand but builds a new string (and possibly a reversed copy), which uses extra memory.

Optimal idea
You do not need a new string. Walk from both ends: skip junk on the left until you see a letter/digit, skip junk on the right the same way, then compare. If every such pair matches, it is a palindrome. This mirrors the definition without storing the filtered string.

Why two pointers work
A palindrome is symmetric: the first meaningful character must match the last meaningful character, the second must match the second-to-last, and so on. Two pointers implement that symmetry directly.

3. The Dry Run

Sample: s = "A man, a plan, a canal: Panama"
Length 30, indices 0–29 (spaces, commas, and : count as non-alphanumeric and are skipped).

We trace the optimal algorithm: advance left / right until both point at alphanumeric characters, then compare lowercased values, then left++, right--.

Compare #	`left` (after skips)	`right` (after skips)	`s[left]`	`s[right]`	Lowercase match?	Next `left`	Next `right`
1	0	29	`A`	`a`	Yes	1	28
2	2	28	`m`	`m`	Yes	3	27
3	3	27	`a`	`a`	Yes	4	26
4	4	26	`n`	`n`	Yes	5	25
5	7	25	`a`	`a`	Yes (skipped `,` and spaces at 5–6 on the left)	8	24
6	9	24	`p`	`P`	Yes	10	23
7	10	21	`l`	`l`	Yes (skipped space at 23 and `:` at 22 on the right)	11	20
8	11	20	`a`	`a`	Yes	12	19
9	12	19	`n`	`n`	Yes	13	18
10	15	18	`a`	`a`	Yes (skipped `,` and space at 13–14 on the left)	16	17
11	17	17	`c`	`c`	Yes (skipped space at 16 on the left)	18	16

After compare 11: left becomes 18 and right becomes 16, so left < right is false — the loop ends.

Result: true.

Invariant (beginner takeaway): After each successful compare, the “outside” alphanumeric characters processed so far form a palindrome prefix/suffix pair; skipping only ignores characters that do not count.

4. Java Solution

Brute Force

Idea: Build filtered lowercase string, compare to its reverse.

Time: O(n) to scan and build, O(n) to reverse/compare → O(n)
Space: O(n) for the filtered string (and possibly reversed copy)

class Solution {
    public boolean isPalindrome(String s) {
        StringBuilder filtered = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (Character.isLetterOrDigit(c)) {
                filtered.append(Character.toLowerCase(c));
            }
        }
        String t = filtered.toString();
        return t.contentEquals(new StringBuilder(t).reverse());
    }
}

Optimal

Idea: Two indices; skip non-alphanumeric; compare case-insensitively.

Time: O(n) — each index moves at most the length of the string.
Space: O(1) — only a few indices and chars.

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

5. The “Java vs. Others” Edge

Character.isLetterOrDigit() and Character.toLowerCase() are the idiomatic Java way to classify and case-fold a single char. In C++, you often use <cctype> helpers like isalnum() and tolower() on unsigned char to avoid UB.
String is immutable in Java. Building a filtered string with repeated + concatenation in a loop creates many temporary objects; StringBuilder is the right tool for the brute-force approach.
The optimal solution avoids allocating the filtered string entirely—important when you care about extra space.
String.contentEquals(CharSequence) compares to another sequence (here a reversed StringBuilder) without an extra String for the reverse if you only need equality (you still allocate the StringBuilder for reverse in the snippet above; alternatively compare indices on filtered with two pointers for another O(n) time, O(n) space variant).

6. Complexity Summary

Approach	Time	Space	Notes
Brute Force	O(n)	O(n)	Simple; allocates filtered (and reverse helper)
Optimal	O(n)	O(1)	Skip and compare from both ends; best for interviews