Valid Palindrome

You are given a string s of printable ASCII characters. Decide whether it is a palindrome when read as a phrase:

• ignore every character that is not an English letter or a digit (spaces, punctuation and symbols do not count);
• treat uppercase and lowercase versions of a letter as the same.

Return true if the remaining characters read the same from left to right as from right to left, and false otherwise. If nothing remains after the filtering, the empty result counts as a palindrome.

Example 1

Example 2

Example 3

Constraints

• 1 <= s.length <= 2 * 105
• s contains only printable ASCII characters.

Pattern Path · Two Pointers · problem 15 of 169

Start simple

Build a filtered lowercase copy and compare it with its reverse: O(n) time but O(n) extra space; checking every substring would be far slower.

The key idea

A palindrome is defined by pairs: the first kept character must equal the last kept one, the second must equal the second-to-last, and so on. Two pointers, left starting at the beginning and right at the end, visit exactly those pairs.

At each step, if s[left] is not a letter or digit, advance left; if s[right] is not, move right back. Once both sit on characters that count, compare them in lowercase. A mismatch proves the answer is false; a match lets both pointers move inward.

When the pointers meet or cross, every pair has been checked, so the answer is true. This also covers the empty case: if there are no letters or digits the pointers just slide past each other without ever comparing.

Each pointer only moves in one direction, so every character is looked at once, and no filtered copy of the string is needed.

Complexity

• Time: O(n)
• Space: O(1)

Python

class Solution:
    def isPalindrome(self, s):
        left, right = 0, len(s) - 1
        while left < right:
            if not s[left].isalnum():
                left += 1           # skip characters that do not count
            elif not s[right].isalnum():
                right -= 1
            elif s[left].lower() != s[right].lower():
                return False
            else:
                left += 1
                right -= 1
        return True

JavaScript

var isPalindrome = function(s) {
  const counts = (ch) => /[a-z0-9]/i.test(ch);
  let left = 0;
  let right = s.length - 1;
  while (left < right) {
    if (!counts(s[left])) {
      left++;               // skip characters that do not count
    } else if (!counts(s[right])) {
      right--;
    } else if (s[left].toLowerCase() !== s[right].toLowerCase()) {
      return false;
    } else {
      left++;
      right--;
    }
  }
  return true;
};

What the interviewer is checking

It tests whether you can apply the two-pointer pattern while cleanly skipping characters, without off-by-one errors or an unnecessary copy of the input.

Mistakes to avoid

• Dropping digits along with punctuation: digits are part of the phrase and must be compared.
• Comparing letters without normalising case, so "Aa" is rejected.
• Skipping a non-alphanumeric character on one side without re-checking the loop bound, which can run a pointer off the string.
• Treating a string of only symbols or spaces as invalid; its cleaned form is empty and therefore a palindrome.

Follow-ups to expect

• What if you may delete at most one character? (On a mismatch, try skipping either side.)
• How would you find the longest palindromic substring? (Expand around each centre.)
• How would you handle Unicode text? (Normalise first; define letters carefully.)

In real software

Text normalisation before comparison (stripping punctuation, folding case) is the same step search engines and deduplication tools apply before matching strings.

Practice next