10.Valid Palindrome

EasyBlind 75Two Pointers · 1/5

Problem

A phrase is a palindrome if, after converting all uppercase letters to lowercase and removing every non-alphanumeric character, 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 this definition, or false otherwise.

Examples

Input:  s = "A man, a plan, a canal: Panama"
Output: true
Explanation: After cleaning it becomes "amanaplanacanalpanama", which reads the same both ways.

Input:  s = "race a car"
Output: false
Explanation: Cleaned: "raceacar" — reversed it is "racaecar".

Input:  s = " "
Output: true
Explanation: Cleaning leaves the empty string, which is a palindrome.

Constraints

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

💡 Key Insight

You do not need to build the cleaned string. Put one pointer at each end and walk them inward, skipping non-alphanumeric characters on the fly and comparing the rest case-insensitively. The first mismatch proves it is not a palindrome; if the pointers meet, it is. That is O(n) time with O(1) extra space.

Clean and Reverse

TimeO(n)SpaceO(n)

Intuition

Follow the definition literally: build the filtered, lowercased string, reverse it, and compare.

Algorithm

Build cleaned by appending Character.toLowerCase(ch) for every ch where Character.isLetterOrDigit(ch).
Build reversed = new StringBuilder(cleaned).reverse().
Return cleaned.equals(reversed).

Visualization

s        = "race a car"
cleaned  = "raceacar"
reversed = "racaecar"
             ^^ differ at index 3 → false

Code

java

class Solution {
    public boolean isPalindrome(String s) {
        StringBuilder cleaned = new StringBuilder();
        for (char ch : s.toCharArray()) {
            if (Character.isLetterOrDigit(ch)) {
                cleaned.append(Character.toLowerCase(ch)); // keep letters/digits, ignore case
            }
        }
        String forward = cleaned.toString();
        String backward = cleaned.reverse().toString();
        return forward.equals(backward);
    }
}

Complexity

Time: O(n) — one pass to clean, one to reverse, one to compare.
Space: O(n) — the cleaned and reversed copies.

Two PointersOptimal

TimeO(n)SpaceO(1)

Intuition

A palindrome mirrors around its centre, so compare the outermost valid characters first and move inward. Instead of deleting junk characters, simply skip them: advance left while it points at a non-alphanumeric character, retreat right likewise, then compare lowercase versions. No copies are made.

Algorithm

left = 0, right = s.length() - 1.
While left < right:
- While left < right and s[left] is not alphanumeric, left++.
- While left < right and s[right] is not alphanumeric, right--.
- If toLowerCase(s[left]) != toLowerCase(s[right]), return false.
- left++, right--.
Return true.

Dry Run

flowchart TD
    A["s = 'race a car'<br/>left=0, right=9"] --> B["r vs r: match"]
    B --> C["left=1, right=8<br/>a vs a: match"]
    C --> D["left=2, right=7<br/>c vs c: match"]
    D --> E["left=3, right=6<br/>e vs space: skip space, right=5"]
    E --> F["e vs a: mismatch"]
    F --> G["return false"]

Code

java

class Solution {
    public boolean isPalindrome(String s) {
        int left = 0;
        int right = s.length() - 1;
        while (left < right) {
            // Skip characters that are not letters or digits
            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; // mirrored characters differ
            }
            left++;
            right--;
        }
        return true;
    }
}

Complexity

Time: O(n) — each pointer moves across the string at most once.
Space: O(1) — just two indices.

Complexity Comparison

Approach	Time	Space
Clean and Reverse	O(n)	O(n)
Two Pointers	O(n)	O(1)

Common Pitfalls

Using Character.isLetter only — digits count too, so "0P" must return false ('0' vs 'p').
Omitting left < right in the inner skip loops — a string of only punctuation like ".," pushes a pointer out of bounds.
Comparing without lowercasing both sides ('A' vs 'a').
Calling cleaned.reverse() on the same StringBuilder you then compare against — reverse() mutates in place, so take toString() first.