4.5.1 — Valid Palindrome

LeetCode 125 · Easy · ★ Blind 75

The problem

Return true if the string reads the same forwards and backwards, ignoring case and every character that is not a letter or digit.

"A man, a plan, a canal: Panama"  →  true
"race a car"                      →  false
" "                               →  true   (nothing left after filtering)

The pattern

A palindrome means position i from the left matches position i from the right. So put one pointer at each end and walk them towards each other, comparing as you go.

The obvious version builds a cleaned copy of the string first and compares it to its reverse. That works and it is two lines. It also allocates two extra strings, so it is O(n) space. Two pointers do the same job in O(1) space by skipping the junk characters in place instead of removing them.

The solution

Python

class Solution:
    def isPalindrome(self, s: str) -> bool:
        l, r = 0, len(s) - 1
        while l < r:
            while l < r and not s[l].isalnum():
                l += 1
            while l < r and not s[r].isalnum():
                r -= 1
            if s[l].lower() != s[r].lower():
                return False
            l += 1
            r -= 1
        return True

TypeScript

function isPalindrome(s: string): boolean {
  const ok = (c: string) => /[a-z0-9]/i.test(c);
  let l = 0, r = s.length - 1;
  while (l < r) {
    while (l < r && !ok(s[l])) l++;
    while (l < r && !ok(s[r])) r--;
    if (s[l].toLowerCase() !== s[r].toLowerCase()) return false;
    l++;
    r--;
  }
  return true;
}

The two inner loops skip characters that do not count. Only when both pointers are sitting on a real letter or digit do you compare.

The l < r inside the inner loops is not optional. Without it, a string of pure punctuation like ",,," sends l running past the end of the string and you get an index error. With it, both pointers stop at the meeting point and the outer loop ends.

Complexity

O(n) time — each pointer only ever moves inwards, so together they take at most n steps.

O(1) space. That is the whole reason to prefer this over the cleaned-copy version. If the string were a gigabyte, the copy version would need another gigabyte.

The two-liner, for comparison

cleaned = ''.join(c.lower() for c in s if c.isalnum())
return cleaned == cleaned[::-1]

Perfectly correct, easier to read, O(n) space. Say it first, then offer the pointer version when asked about memory.

Where this goes next

• Valid Palindrome II — you are allowed to delete one character. When the pointers disagree, try skipping the left one and try skipping the right one, and accept if either remaining stretch is a palindrome.
• Palindromic Substrings and Longest Palindromic Substring — expand outward from each centre instead of inward from the ends. Chapter 4.23.
• Reverse a string in place, remove duplicates in place — the same converging-pointer shape.

Next: 4.5.2 Two Sum II — the same two pointers, but now the rule for which one moves has to be proved rather than guessed.