Valid Palindrome

The problem

You are given a string text. Ignore every character that is not a letter or a digit, and ignore the difference between uppercase and lowercase. Return true if what is left reads the same forwards and backwards. Otherwise return false.

Example 1

Input: text = "Top, spot!"

Output: true

Keeping only letters in lowercase gives “topspot”, which reads the same both ways.

text

T0o1p2,3␣4s5p6o7t8!9

Example 2

Input: text = "Was it a cat"

Output: false

The letters are “wasitacat”. Backwards that is “tacatisaw”, which is different.

Example 3

Input: text = ".,!"

Output: true

No letters or digits are left. An empty string reads the same both ways.

Constraints

• 1 ≤ n ≤ 200,000, where n is the length of text
• text holds printable ASCII characters only.

Clarifying questions

Do digits count?

Yes. Letters and digits both count. So "0P" is not a palindrome.

Does case matter?

No. "T" and "t" are treated as the same letter.

What if nothing is left after cleaning?

Then the answer is true. An empty string is a palindrome.

Can we build a new string?

Yes, but it costs O(n) memory. The two-pointer approach avoids it.

Spot the pattern

A palindrome compares the first character with the last, the second with the second to last, and so on. That is a pair of positions moving toward each other from both ends: the two-pointer pattern. Skipping the extra characters fits in the same loop.

Solutions

Clean copyO(n)Two pointersO(n), O(1) space

Show all

This problem has two approaches. Both are O(n) time; the second one saves the copy.

Clean copy O(n)

The idea

Build a clean copy of the string: walk it once and keep only the letters and digits, each in lowercase. Then check the copy against its mirror. Compare position i with position clean_length − 1 − i for the first half of the copy. If any pair differs, it is not a palindrome.

It is simple and fast. The only cost is the extra copy.

Walkthrough

text

T0o1p2,3␣4s5p6o7t8!9

clean

empty

1. clean = []
2. for character in text:
3. if character.isalnum():
4. clean.append(character.lower())
5. clean_length = len(clean)
6. for i in range(clean_length // 2):
7. if clean[i] != clean[clean_length - 1 - i]:
8. return False
9. return True

First build a clean copy: keep only letters and digits, all in lowercase.

← BackStep →Play1 / 15

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    // Clean copy: keep letters and digits in lowercase, then compare with the mirror.
    // Two passes, O(n) time. The copy takes O(n) memory.
    public boolean isPalindrome(String text) {
        StringBuilder clean = new StringBuilder();
        for (char character : text.toCharArray()) {
            if (Character.isLetterOrDigit(character)) {
                clean.append(Character.toLowerCase(character));
            }
        }
        int cleanLength = clean.length();
        // Each pair is (i, its mirror). Half the pairs cover them all.
        for (int i = 0; i < cleanLength / 2; i++) {
            if (clean.charAt(i) != clean.charAt(cleanLength - 1 - i)) return false;
        }
        return true;
    }
}

Big O

Time O(n)Space O(n)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   There are two loops, one after the other. The first checks one character and maybe adds it to the copy. The second compares one pair. Each run is 1 step.

   1. clean = []
   2. for character in text:
   3. if character.isalnum():
   4. clean.append(character.lower())
   5. clean_length = len(clean)
   6. for i in range(clean_length // 2):
   7. if clean[i] != clean[clean_length - 1 - i]:
   8. return False
   9. return True

2. 2 Count the runs on Example 1

   Example 1 has 10 characters, so the cleaning loop runs 10 times. The copy “topspot” has 7 letters, so the compare loop runs 7 // 2 = 3 times.

   10 + 3 = 13 runs.

   loop	clean	compare
   runs on Example 1	10 (one per character)	3 (half of 7)

3. 3 Write the count for any n

   The copy has at most n characters, so the compare loop runs at most n / 2 times:

   n + n / 2 = 1.5n

   Check it with Example 1: the copy is shorter than n, so 13 is below 1.5 × 10 = 15.

4. 4 Keep only the part that grows fastest

   Drop the 1.5. A fixed factor does not change how the work grows. What is left is n.

   So the time is O(n).

5. S Space: count the extra memory the same way

   The copy clean can hold up to n characters, when every character is a letter or digit. So the space is O(n).

   clean (up to n characters)characteri

Two pointers O(n), O(1) space

The idea

Skip the copy. Put a pointer left at the start and a pointer right at the end. On each step:

• If left points at something that is not a letter or digit, move left one step right.
• Else, if right points at such a character, move right one step left.
• Else compare the two letters in lowercase. If they differ, return false. If they match, move both pointers inward.

Stop when the pointers meet. A middle letter with no partner needs no check.

Why it is correct: the pointers visit exactly the pairs the clean copy would compare, in the same order, just without building the copy.

Walkthrough

text

T0o1p2,3␣4s5p6o7t8!9

leftright

1. left, right = 0, len(text) - 1
2. while left < right:
3. if not text[left].isalnum():
4. left += 1
5. elif not text[right].isalnum():
6. right -= 1
7. elif text[left].lower() != text[right].lower():
8. return False
9. else:
10. left += 1; right -= 1
11. return True

Put one pointer at each end. Compare from the outside in, and skip anything that is not a letter or digit.

← BackStep →Play1 / 8

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    // Two pointers from both ends, skipping anything that is not a letter or digit.
    // Each step moves a pointer inward, so O(n) time. No copy, so O(1) memory.
    public boolean isPalindrome(String text) {
        int left = 0, right = text.length() - 1;
        while (left < right) {
            // Skip one character at a time, so the loop never jumps past the other pointer.
            if (!Character.isLetterOrDigit(text.charAt(left))) left++;
            else if (!Character.isLetterOrDigit(text.charAt(right))) right--;
            else if (Character.toLowerCase(text.charAt(left))
                    != Character.toLowerCase(text.charAt(right))) return false;
            else {
                left++;
                right--;
            }
        }
        // The pointers met or crossed with every pair matched.
        return true;
    }
}

Big O

Time O(n)Space O(1)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   Each run of the loop does one check or one compare, and then moves at least one pointer inward. That is a fixed amount of work, so each run is 1 step.

   1. left, right = 0, len(text) - 1
   2. while left < right:
   3. if not text[left].isalnum():
   4. left += 1
   5. elif not text[right].isalnum():
   6. right -= 1
   7. elif text[left].lower() != text[right].lower():
   8. return False
   9. else:
   10. left += 1; right -= 1
   11. return True

2. 2 Count the runs on Example 1

   Example 1 has 10 characters, so the gap between the pointers starts at 9. Each run shrinks it by 1 (a skip) or by 2 (a match). The table shows the 6 runs until the gap is 0.

   6 runs.

   run	1	2	3	4	5	6
   what happened	skip "!"	match T, t	match o, o	match p, p	skip ","	skip "␣"
   gap after	8	6	4	2	1	0

3. 3 Write the count for any n

   The gap starts at n − 1 and every run shrinks it by at least 1. So the loop runs at most:

   n − 1 times

   Check it with Example 1: 6 runs, below 10 − 1 = 9, because matches move both pointers.

4. 4 Keep only the part that grows fastest

   Drop the − 1. One run more or less does not change how the work grows. What is left is n.

   So the time is O(n).

5. S Space: count the extra memory the same way

   The code keeps only left and right. That is 2 numbers for any n, so the space is O(1).

   leftright

Common mistake

Skipping with an inner while loop and no bound

Writing while not text[left].isalnum(): left += 1 inside the main loop runs past the end on a string like “.,!”. If you skip with inner loops, also check left < right in them. The version above skips one character per run, so it can never overshoot.

Tested at the limits

2,000 random texts of letters, digits, spaces and punctuation. Half are real palindromes with mixed case, and some have no letters or digits at all. The clean copy and the two pointers gave the same answer every time.

Largest inputs	Result
About 187,000 characters (close to the most allowed), a true palindrome with punctuation, so both pointers walk all the way in. Two pointers.	0.01 s, and under 0.001 MB of extra memory: just the two pointers.
About 187,000 characters, same text. Clean copy.	0.02 s, and about 7 MB of extra memory: the cleaned copy of 150,000 letters and digits.