Valid Palindrome

Examples

Input: s = "A man, a plan, a canal: Panama"
Output: true

Stripping out everything except letters and digits, and lowercasing, gives "amanaplanacanalpanama", which reads the same both ways.

Input: s = "race a car"
Output: false

Cleaned up, this is "raceacar" — reversed it's "racaecar", which is different.

Input: s = ".,"
Output: true

There are no letters or digits at all here, so after cleaning it up there's nothing left — and an empty string trivially reads the same both ways.

Constraints

• 1 <= s.length <= 2 * 10^5

• s consists only of printable ASCII characters.

Approach

The most straightforward way to solve this is to build a cleaned-up version of the string (letters and digits only, all lowercase), and then check whether that cleaned string equals its own reverse. This works, but it means allocating a whole new string just to compare it against another new string.

A leaner way: skip building anything new. Keep one pointer at the start of the original string and one at the end, and walk them toward each other. At each step, skip past any character that isn't a letter or digit. Once both pointers are sitting on "real" characters, compare them (ignoring case) — if they ever don't match, the string isn't a palindrome. If the pointers meet without ever disagreeing, it is.

Solutions

Brute Force — Clean, Then Compare to Reverse

Build a new string containing only the lowercased letters and digits from the input, then compare that string to its own reverse. Simple to reason about, but it does extra work building and reversing a second string.

function isPalindrome(s) {
  const cleaned = s.toLowerCase().replace(/[^a-z0-9]/g, "");
  const reversed = cleaned.split("").reverse().join("");
  return cleaned === reversed;
}

Time: O(n) · Space: O(n)

Optimal — Two Pointers

Walk one pointer in from the left and one in from the right, skipping over any character that isn't a letter or digit. Compare the two pointers' characters (case-insensitively) as they close in on the middle. No extra string is ever built.

function isPalindrome(s) {
  const isAlnum = (c) => /[a-z0-9]/i.test(c);
  let left = 0;
  let right = s.length - 1;

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

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

    left++;
    right--;
  }

  return true;
}

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