Valid Palindrome

EasyStrings · Two Pointers🧩 String Manipulation LeetCode #125 ↗Updated Oct 30, 2026

Problem

Given a string s, decide whether it reads the same forwards and backwards once you ignore every character that is not a letter or digit and treat upper- and lower-case letters as equal. Return true or false.

Input"A man, a plan, a canal: Panama"Outputtrue

Input"race a car"Outputfalse

Input" "Outputtrue

1 ≤ s.length ≤ 2·10⁵ · s is printable ASCII · empty-after-cleaning counts as a palindrome

Try it yourself

Java

class Solution {
    public boolean isPalindrome(String s) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

You never need the cleaned string. Two pointers walking inwards can simply skip junk characters on the fly and compare the rest case-insensitively.

PatternString Manipulation

Instinct Reading, comparing or rebuilding text character by character? Walk indices on a char[] and build output with a StringBuilder, never with + in a loop.

Memory hack Chars in an array, pointers on the ends, builder at the back - strings are just arrays wearing a costume.

Open the String Manipulation guide →

Approaches

Brute ForceClean, Reverse & Compare

Time O(n)Space O(n)

Build a filtered lower-case copy of s, build its reverse, and check the two are equal. A palindrome is by definition equal to its reverse.

Java

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

Simplest to write, but allocates two extra strings and never exits early.

BetterClean, then Two Pointers

Time O(n)Space O(n)

Keep the cleaned copy but drop the reversed one: compare cleaned[left] with cleaned[right] while moving the pointers inwards, returning false at the first mismatch.

Java

public boolean isPalindrome(String s) {
    StringBuilder cleaned = new StringBuilder();
    for (char c : s.toCharArray()) {
        if (Character.isLetterOrDigit(c)) {
            cleaned.append(Character.toLowerCase(c));
        }
    }
    int left = 0, right = cleaned.length() - 1;
    while (left < right) {
        if (cleaned.charAt(left) != cleaned.charAt(right)) return false;
        left++;
        right--;
    }
    return true;
}

One buffer instead of two and an early exit, but still O(n) extra memory.

OptimalIn-place Two Pointers (Skip Junk)

Time O(n)Space O(1)

Run the pointers directly on s. Before each comparison, advance left and retreat right past non-alphanumerics. Each index is visited at most once overall, so the work stays linear with no copy.

Java

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

Dry run"Ab,bA"

l leftr right changed

1
A
l
b

,

b

A
r
a == a → move in
2
A

b
l
,

b
r
A

b == b → move in
3
A

b

,
l r
b

A

l == r → true ✔

Single pass, constant memory, exits on the first mismatch.

Pro tip

Keep the left < right guard inside the skip loops, or a string of only symbols runs off the end.

At a glance

Level	Approach	Time	Space
Brute Force	Clean, Reverse & Compare	`O(n)`	`O(n)`
Better	Clean, then Two Pointers	`O(n)`	`O(n)`
Optimal	In-place Two Pointers (Skip Junk)	`O(n)`	`O(1)`

Common pitfalls

Forgetting digits — "0P" is not a palindrome ('0' != 'p').
Comparing without lower-casing — 'A' != 'a'.
Skip loops without the left < right guard → index out of bounds.

Interview tips

Clarify what counts as alphanumeric and that empty strings are palindromes.
Mention the cleaned-copy version first, then remove the copy for O(1) space.
Know the follow-up: Valid Palindrome II (delete at most one char).

Pattern

Converging two pointers → symmetric checks on a sequence (palindromes, pair sums on sorted data).

My notes saved in this browser