Valid Palindrome

Easy Arrays & Hashing Two Pointer Original on LeetCode

Valid Palindrome is a easy arrays & hashing problem solved with the two pointer pattern. The best approach, optimal (two pointers, skipping in place), runs in O(n) time and O(1) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (clean, then compare with the reverse) up.

Problem

A phrase counts as a palindrome if, after turning every uppercase letter into lowercase and throwing away every character that is not a letter or a digit, it reads the same from left to right as from right to left.

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

Examples

Example 1

Input
s = "Step on no pets!"
Output
true
Why
Keeping only letters and digits in lowercase gives "steponnopets", which reads the same both ways.

Example 2

Input
s = "Race a car, 2x"
Output
false
Why
The cleaned text is "raceacar2x"; its first and last characters already differ.

Example 3

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

Constraints

  • 1 <= s.length <= 2 * 10^5
  • s consists of printable ASCII characters.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 14 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (clean, then compare with the reverse)O(n)O(n)
Optimal (two pointers, skipping in place)O(n)O(1)

1Brute force (clean, then compare with the reverse)

TimeO(n)One pass to clean, one to reverse, one to compare.
SpaceO(n)The cleaned string and its reverse.

Build a new string with only the letters and digits of s, lowercased. It is a palindrome exactly when it equals its own reverse.

  1. For each character, if it is a letter or digit, append its lowercase form.
  2. Return cleaned == reverse(cleaned).
class Solution {
    public boolean isPalindrome(String s) {
        StringBuilder sb = new StringBuilder();
        for (char c : s.toCharArray())
            if (Character.isLetterOrDigit(c)) sb.append(Character.toLowerCase(c));
        String cleaned = sb.toString();
        return cleaned.equals(sb.reverse().toString());
    }
}

2Optimal (two pointers, skipping in place)

TimeO(n)Each pointer moves across each character at most once.
SpaceO(1)Two indices only.

Put l at the start and r at the end. Move l forward past characters that are not letters or digits, and r backward the same way. Compare the two characters in lowercase; a mismatch means false. Otherwise step both inward. No copy is made.

  1. l = 0, r = n - 1.
  2. While l < r: skip non-alphanumerics from the left and from the right (keeping l < r).
  3. If lower(s[l]) != lower(s[r]) return false; else l++, r--.
  4. Return true.
class Solution {
    public boolean isPalindrome(String s) {
        int l = 0, r = s.length() - 1;
        while (l < r) {
            while (l < r && !Character.isLetterOrDigit(s.charAt(l))) l++;
            while (l < r && !Character.isLetterOrDigit(s.charAt(r))) r--;
            if (Character.toLowerCase(s.charAt(l)) != Character.toLowerCase(s.charAt(r))) return false;
            l++;
            r--;
        }
        return true;
    }
}

Edge cases to test

  • No letters or digits at all (true)
  • A single alphanumeric character
  • Mixed upper and lower case of the same letter
  • Digits next to letters, such as "0P" (digits are kept and are not equal to letters)
  • Long runs of punctuation and spaces at one end only

Hints

Hint 1

First decide which characters matter: letters and digits only, with upper and lower case treated as the same.

Hint 2

You could build the cleaned string and compare it with its reverse, but that copies the input.

Hint 3

Use two pointers from both ends; skip characters that do not count, and compare the rest case-insensitively.

FAQ

What is the best time complexity for Valid Palindrome?

Optimal (two pointers, skipping in place) runs in O(n) time and O(1) extra space. Each pointer moves across each character at most once.

Which pattern does Valid Palindrome use?

It is a arrays & hashing problem that uses the two pointer pattern. Other problems with the same pattern: Two Sum II - Input Array Is Sorted, Valid Triangle Number, Container With Most Water.

Is there a brute force solution for Valid Palindrome?

Yes. Brute force (clean, then compare with the reverse) takes O(n) time and O(n) space. Build a new string with only the letters and digits of s, lowercased.

Which edge cases should I test for Valid Palindrome?

No letters or digits at all (true); A single alphanumeric character; Mixed upper and lower case of the same letter; Digits next to letters, such as "0P" (digits are kept and are not equal to letters); Long runs of punctuation and spaces at one end only.