Valid Palindrome

The problem

Given a string s, return true if it is a palindrome and false if it is not. A palindrome reads the same forward and backward. Only the letters a to z and the digits 0 to 9 count. Upper and lower case are treated as the same letter. Every other character, such as a space or a question mark, is ignored. A string with no letters or digits at all counts as a palindrome.

What to write

function solve(s: string): boolean

Input
s = "Was it a car or a cat I saw?"

Output
true

Input
s = "tab a cat"

Output
false

Constraints

0–10,000 ASCII characters; only letters and digits are retained.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   Spaces, punctuation and letter case do not count. So "Was it a car" and "wasitacar" are the same text for this question, and you may work with whichever form is easier. With at most 10,000 characters, one extra pass over the text costs almost nothing.

2. Hint 2: Ask a smaller question

   Check the word "level" by hand. Which letter must the first one equal? Which must the second one equal? And which letter do you never have to compare with anything?

3. Hint 3: Name the pattern

   A palindrome is decided by mirrored pairs: first with last, second with second to last. Keep two positions, called pointers, one at each end, and move them toward each other while the pairs match. This is opposing two pointers. Read the lesson on opposing two pointers.

4. Hint 4: State the invariant

   Everything outside the two pointers is already matched with its mirror character. So if the pointers meet or pass each other without finding a difference, every pair matched and the text is a palindrome.

5. Hint 5: Sketch the pseudocode

   clean = s in lowercase with only its letters and digits. left = 0, right = last position of clean. While left < right: if the characters at left and right differ, return false; otherwise add 1 to left and subtract 1 from right. Return true.

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

Keep only the letters and digits, in lowercase. Then compare the first character with the last, the second with the second to last, and so on until the two positions meet or pass each other.

The slow way

Strip the text down to its lowercase letters and digits, build a second copy of that in reverse order, and test whether the two are equal. It is correct and short, but it builds a whole second copy before it compares a single character, even when the first and last letters already differ.

The insight

Reading backward is the same as reading from the other end. So the first character must equal the last, the second must equal the second to last, and so on. Two positions that walk toward each other from both ends check exactly those pairs, and the first pair that differs settles the answer.

Step by step

1. Keep only the letters and digits, all in lowercase. The rules say that case, spaces and punctuation do not count. Removing them once, at the start, leaves a text in which every character must equal its mirror.
2. Start one pointer at each end of the cleaned text. A pointer is a position in the text, kept in a variable. The first and last characters are the outermost mirrored pair, so the check starts there.
3. Two characters that differ mean it is not a palindrome. One pair that does not match is enough. The text already reads differently from its two ends, so the characters between them no longer matter.
4. They match, so move both pointers one step inward. This pair is settled. The next pair to check sits directly inside it: one place later on the left, one place earlier on the right.
5. The pointers met or passed each other, so every pair matched. When the pointers meet or pass each other, no unchecked pair is left. A single character in the middle is its own mirror and needs no check.

The same numbered steps are the comments in each solution.

function solve(s) {
  // 1. Keep only the letters and digits, all in lowercase
  const clean = s.toLowerCase().replace(/[^a-z0-9]/g, "");
  // 2. Start one pointer at each end of the cleaned text
  let left = 0,
    right = clean.length - 1;
  while (left < right) {
    // 3. Two characters that differ mean it is not a palindrome
    if (clean[left] !== clean[right]) return false;
    // 4. They match, so move both pointers one step inward
    left++;
    right--;
  }
  // 5. The pointers met or passed each other, so every pair matched
  return true;
}

function solve(s: string): boolean {
  // 1. Keep only the letters and digits, all in lowercase
  const clean = s.toLowerCase().replace(/[^a-z0-9]/g, "");
  // 2. Start one pointer at each end of the cleaned text
  let left = 0,
    right = clean.length - 1;
  while (left < right) {
    // 3. Two characters that differ mean it is not a palindrome
    if (clean[left] !== clean[right]) return false;
    // 4. They match, so move both pointers one step inward
    left++;
    right--;
  }
  // 5. The pointers met or passed each other, so every pair matched
  return true;
}

def solve(s):
    # 1. Keep only the letters and digits, all in lowercase
    clean = "".join(ch for ch in s.lower() if ch.isascii() and ch.isalnum())
    # 2. Start one pointer at each end of the cleaned text
    left, right = 0, len(clean) - 1
    while left < right:
        # 3. Two characters that differ mean it is not a palindrome
        if clean[left] != clean[right]:
            return False
        # 4. They match, so move both pointers one step inward
        left += 1
        right -= 1
    # 5. The pointers met or passed each other, so every pair matched
    return True

Example 1, traced

Input
s = "Was it a car or a cat I saw?"

Output
true

Why it works

Everything outside the two pointers is already matched with its mirror. Each round either finds a pair that differs, which proves the text is not a palindrome, or settles one more pair and moves inward. When the pointers meet or pass each other, every pair has been checked, so the text reads the same in both directions.

Time and space

Time O(n), extra space O(n). Cleaning takes a couple of passes over the n characters. After that, every round moves both pointers one step, so the loop runs at most n / 2 times. Together that is O(n) time. The cleaned copy can be as long as the input, which is the O(n) space.

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• Turn the text to lowercase before you compare. Without that, the W and the w at the two ends of example 1 count as different, and the answer comes out false.
• Keep the digits when you clean. If only letters are kept, "0P" shrinks to "p", which is a palindrome, but the right answer is false.
• Loop while left is before right, not while left is different from right. In a cleaned text of even length, such as "abba", the pointers pass each other without ever being equal, and the loop runs off both ends.

Pattern

Opposing two pointers.

Keep going