Problem 3.1 · StringsEasy

Valid Palindrome

What it teaches: Two pointers that skip characters you don't care about, without building a cleaned copy.

Practise it on judges as “Valid Palindrome”.

The problem

A phrase is a palindrome if, after converting uppercase letters to lowercase and removing all non-alphanumeric characters, it reads the same forwards and backwards. Given a string s, return true if it's a palindrome.

Example 1

Input: s = "A man, a plan, a canal: Panama"
Output: true

Cleaned: "amanaplanacanalpanama".

Example 2

Input: s = "race a car"
Output: false

Example 3

Input: s = " "
Output: true

Nothing remains after cleaning, and an empty string is a palindrome.

Constraints

1 ≤ s.length ≤ 2 × 10⁵
s contains printable ASCII characters

Pattern clues in the wording

→ Compare the first with the last, the second with the second-to-last
→ Skip characters that don't count
→ O(1) extra space is possible

These clues point to Two Pointers: Opposite Ends: Start one pointer at each end and move them towards each other, using a rule to decide which one moves.

Stuck? Take one hint at a time

Solution.java · starter

class Solution {
    public boolean isPalindrome(String s) {
        int left = 0, right = s.length() - 1;
        return true;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	s = "A man, a plan, a canal: Panama"	true
2	s = "race a car"	false
3	s = " "	true

+ 2 hidden tests the code runner will check

From slow to fast

Approaches

1. Clean, then compare with the reverse · O(n)2. Optimal: two pointers, skipping in place · O(n)

Clean, then compare with the reverse

Time O(n) Space O(n)

Build a lowercase string of only letters and digits, then check it equals its reverse.

Approach 1

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));
        String forward = clean.toString();
        return forward.equals(clean.reverse().toString());
    }
}

Verdict: Clear and correct, but makes two extra strings.

Optimal: two pointers, skipping in place

Time O(n) Space O(1)

left starts at 0, right at the end. Move left forward past non-alphanumeric characters and right backward the same way. Compare the lowercase forms; if different, return false; else step both inwards.

▶ Dry run: Skipping punctuations = "a,b:A"

↑L

↑R

Step 1/3'a' vs 'A': equal ignoring case. Step both inwards.

Approach 2

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++;
            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;
    }
}

Verdict: One pass, no copies.

Before you submit

Edge cases and common mistakes

Test these inputs

Only punctuation or spaces → true
Single character
Digits mixed with letters, e.g. "0P" → false

Mistakes people make

Forgetting left < right inside the skipping loops, so a pointer runs off the end on strings like "!!!".
Comparing without lowercasing.
Treating digits as removable (they count).

Interview

Follow-up questions

What if you may delete at most one character?

What if the string is a stream too large for memory?

Command Palette