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

Topic	Description
Two Pointers	Scan a sorted array or string from both ends at once to find pairs, remove duplicates, or reverse data in O(n).
Merge Sorted Array	Merge two sorted arrays into one sorted array in place.
Remove Duplicates from Sorted Array	Remove duplicate values from a sorted array in place and return the new length.
Move Zeroes	Move every zero in an array to the end while keeping the other numbers in order.
Two Sum II - Input Array Is Sorted	Find two numbers in a sorted array that add up to a target value.
3Sum	Find every unique triplet of numbers in an array that adds up to zero.