Valid Palindrome Solutions & Complexity

1. Define the problem

Valid Palindrome

A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Given a string s, return true if it is a palindrome, or false otherwise. Use two pointers starting at the left and right ends, skipping non-alphanumeric characters and comparing lowercased characters as they converge toward the middle.

Constraints

1 ≤ s.length ≤ 2 × 10⁵
s consists only of printable ASCII characters

Example

Inputs = "A man, a plan, a canal: Panama"

Outputtrue

Explanation After removing non-alphanumeric characters and lowercasing, the string becomes "amanaplanacanalpanama", which reads the same forward and backward.

2. Know the words first

In plain terms

Palindrome: A word or phrase that reads exactly the same forwards and backwards, like 'level' or 'racecar'.
Alphanumeric: A letter or a digit — so spaces, punctuation, and other symbols are not alphanumeric.

3. Visualize the solution

Converge two pointers, skipping non-alphanumeric characters

Statusinit

The row is the string "Ta, cat". left starts at 0 and right starts at 6.

What happens in this step

left = 0 (value 'T'), right = 6 (value 't')

Both characters are letters, so we compare them in lowercase: 't' vs 't'. They match, so both pointers step inward.

Step 1 of 4

Steps to visualize

Place one pointer at the start and one at the end of the string.
Move the left pointer right while it sits on a non-alphanumeric character.
Move the right pointer left while it sits on a non-alphanumeric character.
Compare the lowercased characters at both pointers; if they differ, return false.
Move both pointers one step toward the middle and repeat.
If the pointers meet or cross without a mismatch, the string is a palindrome.

4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Converge two pointers, skipping non-alphanumeric characters

Statusinit

The row is the string "Ta, cat". left starts at 0 and right starts at 6.

What happens in this step

left = 0 (value 'T'), right = 6 (value 't')

Both characters are letters, so we compare them in lowercase: 't' vs 't'. They match, so both pointers step inward.

Step 1 of 4

5. Solution

Solution

solution.tsTypeScript

function isPalindrome(s) {
  const isAlphanumeric = (ch) => /[a-z0-9]/i.test(ch);

  let left = 0;
  let right = s.length - 1;

  while (left < right) {
    while (left < right && !isAlphanumeric(s[left])) {
      left++;
    }
    while (left < right && !isAlphanumeric(s[right])) {
      right--;
    }

    if (s[left].toLowerCase() !== s[right].toLowerCase()) {
      return false;
    }

    left++;
    right--;
  }

  return true;
}

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

6. Test cases

Test cases

Input	Expected	Covers
`s = "A man, a plan, a canal: Panama"`	`true`	example from the docstring
`s = "race a car"`	`false`	valid alphanumeric string that is not a palindrome
`s = " "`	`true`	string with no alphanumeric characters is trivially a palindrome
`s = "a"`	`true`	smallest valid input, a single character
`s = "Was it a car or a cat I saw?"`	`true`	mixed case and multiple punctuation marks throughout
`s = "12321"`	`true`	numeric characters treated as alphanumeric
`s = "ab"`	`false`	even-length string that fails on the first comparison

Valid Palindrome