Valid Palindrome

A phrase is a palindrome if, after turning every uppercase letter into lowercase and removing every character that is not a letter or a digit, it reads the same forward and backward. Given a string s, return true if it is a palindrome. This is LeetCode 125.

Example 1
Input: s = "A man, a plan, a canal: Panama"
Output: true
Explanation: "amanaplanacanalpanama" is a palindrome.
Example 2
Input: s = "race a car"
Output: false
Explanation: "raceacar" is not a palindrome.
Example 3
Input: s = " "
Output: true
Explanation: after cleaning, the string is empty, and an empty string reads the same both ways.

How to Think About It

Step 1: The simple way

Build a cleaned, lowercase copy of the string, then compare it with its reverse. That works but uses O(n) extra space.

Step 2: Compare from both ends instead

A palindrome's first character matches its last, its second matches its second to last, and so on. Put lo at the start and hi at the end and compare as they move toward each other.

Step 3: Skip what does not count

At each step:

  • if s[lo] is not a letter or digit, move lo right and try again;
  • if s[hi] is not a letter or digit, move hi left and try again;
  • otherwise compare them ignoring case. A mismatch means it is not a palindrome. A match moves both pointers inward.

If the pointers meet without a mismatch, the string is a palindrome.

Walkthrough

s = "race a car" (indices 0 to 9).

lo (char)hi (char)Decision
0 (r)9 (r)match
1 (a)8 (a)match
2 (c)7 (c)match
3 (e)6 (space)skip the space on the right
3 (e)5 (a)e ≠ a: return false

Java Solution

The method compares characters from both ends, skipping anything that is not a letter or a digit:

  • One step per pass: each pass either skips one character on one side or compares a pair, so no character is jumped over.
  • Digits count: Character.isLetterOrDigit keeps digits, so "0P" compares '0' with 'P' and returns false.
  • Case: Character.toLowerCase on both sides makes "Aa" a palindrome.
  • Nothing to compare: " " or ".,;" skip until the pointers meet and return true, as the problem requires for an empty cleaned string.

Using Character.isLetter drops digits: "0P" then skips the '0' and returns true, although "0p" is not a palindrome.

Java
public class ValidPalindrome {

    public static boolean isPalindrome(String s) {
        int lo = 0;
        int hi = s.length() - 1;
        while (lo < hi) {
            char a = s.charAt(lo);
            char b = s.charAt(hi);
            if (!Character.isLetterOrDigit(a)) {
                lo++;                         // skip spaces and punctuation
            } else if (!Character.isLetterOrDigit(b)) {
                hi--;
            } else if (Character.toLowerCase(a) != Character.toLowerCase(b)) {
                return false;
            } else {
                lo++;
                hi--;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        System.out.println(isPalindrome("A man, a plan, a canal: Panama"));   // true
        System.out.println(isPalindrome("race a car"));                       // false
        System.out.println(isPalindrome(" "));                                // true
    }
}

The original implementation, ValidPalindrome.java, is on GitHub.

Complexity

  • Time: O(n). lo only moves right and hi only moves left, so the loop runs at most n times with one check per pass.
  • Space: O(1). Two indices and two chars; no cleaned copy of the string is built, which would cost O(n).

If one character may be deleted, see Valid Palindrome II. Two Pointers Basics shows the other ways two pointers can move through a string.