Valid Palindrome

EasyTwo PointersNeetCode 150JuniorOpen on LeetCodeUpdated Sep 21, 2026

You're given a string s. Return true if it reads the same forward and backward after you drop every character that isn't a letter or digit and treat uppercase and lowercase as equal. Return false otherwise. Digits count, so "0P" is not a palindrome. A string with no letters or digits at all counts as a palindrome.

Examples

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

Dropping spaces and punctuation and lowercasing gives "amanaplanacanalpanama", which reads the same in both directions.

s = "race a car" returns false

Cleaned, it becomes "raceacar". Reversed it reads "racaecar", and the two differ at the fourth character (e vs a).

s = " " returns true

The only character is a space, so nothing is left after filtering. An empty string reads the same both ways.

Constraints

1 <= s.length <= 2 * 10^5

Hints

Hint 1

What two indices would you compare if you wanted to mirror the string from the outside in?

Hint 2

A pointer toward the approach

Hint 3

The full approach, step by step

Drill This: Your Approach First

Answer, Then Reveal

In two or three sentences, how would you solve it and what's the complexity?

Skip to Reading

Approach

Walk one index in from each end. On each side, skip characters that aren't letters or digits, then compare the two characters lowercased; any mismatch means false. If the indices meet, every mirrored pair matched, so the string is a palindrome. Working in place avoids building a cleaned copy of the string.

Time

O(n)

Space

O(1)

Pitfall

Filter with an alphanumeric check, not a letters-only check: with letters only, "0P" shrinks to "p" and wrongly returns true. Each skip loop also needs its own left < right guard, or a string of pure punctuation runs off the end.

Solutions

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

class Solution:
    def isPalindrome(self, s: str) -> bool:
        left, right = 0, len(s) - 1
        while left < right:
            while left < right and not s[left].isalnum():
                left += 1
            while left < right and not s[right].isalnum():
                right -= 1
            if s[left].lower() != s[right].lower():
                return False
            left += 1
            right -= 1
        return True