Valid Palindrome

Easy Problem 16 of 151 Java and Python

Problem

A phrase is a palindrome if, after converting uppercase letters to lowercase and removing every character that is not a letter or digit, it reads the same forwards and backwards.

Given a string s, return true if it is a palindrome and false otherwise.

Example 1

Input: s = "A man, a plan, a canal: Panama"
Output: true
Why: Cleaned up, it becomes "amanaplanacanalpanama".

Example 2

Input: s = "race a car"
Output: false
Why: "raceacar" is not the same reversed.

Example 3

Input: s = " "
Output: true
Why: Nothing is left after cleaning, and an empty string is a palindrome.

Constraints

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

Explanation

A palindrome mirrors around its middle, so compare the first and last useful characters, then move inwards.

You do not need to build the cleaned string first: let each pointer skip characters that are not letters or digits.

Approach 1 · Naive

Clean, then compare with the reverse

Time O(n)
Space O(n)

Build a new string with only lowercase letters and digits, and compare it with its reverse.

Keep only alphanumeric characters, lowercased.
Return whether the cleaned string equals its reverse.

Java

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

Python

class Solution:
    def isPalindrome(self, s: str) -> bool:
        clean = [c.lower() for c in s if c.isalnum()]
        return clean == clean[::-1]

Approach 2 · Optimal

Two pointers, no copy

Time O(n)
Space O(1)

Start one pointer at each end. Skip anything that is not a letter or digit, compare the two characters case-insensitively, and move both inwards.

Set left = 0, right = n - 1.
While left < right: move left right past non-alphanumerics, and right left past non-alphanumerics.
If the lowercased characters differ, return false; otherwise move both pointers.
Return true.

Java

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

Python

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

Complexity compared

Approach	Time	Space
Naive Clean, then compare with the reverse	O(n)	O(n)
Optimal Two pointers, no copy	O(n)	O(1)

Key takeaways

Check left < right inside the skipping loops too, or a string of only punctuation runs off the end.

Your notes

Saved in this browser as you type.

Solved it on your own?

Mark it done to track your progress, or star it to come back before an interview.

Next problem