Valid Palindrome

Problem Statement

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.

Alphanumeric characters include letters (a-z, A-Z) and numbers (0-9).

Given a string s, return true if it is a palindrome, or false otherwise.

Brute Force

Create a new string containing only alphanumeric characters, convert it to lowercase, then compare it with its reversed version.

It works, but it uses O(n) extra space to store the cleaned string.

function isPalindrome(s) {
  const cleaned = s.replace(/[^a-zA-Z0-9]/g, "").toLowerCase();

  const reversed = cleaned.split("").reverse().join("");

  return cleaned === reversed;
}

Time: O(n)    Space: O(n) — the cleaned and reversed strings require extra memory.

Better Approach: Two Pointers

Instead of creating a cleaned string, use two pointers directly on the original string.

Put one pointer at the start and one at the end.

• If left points to a non-alphanumeric character, move it forward.
• If right points to a non-alphanumeric character, move it backward.
• Once both pointers point to valid characters, compare them ignoring case.
• If they don't match, return false.
• Otherwise, move both pointers inward.

function isPalindrome(s) {
  let left = 0;
  let right = s.length - 1;

  const isAlphaNumeric = (ch) => /[a-zA-Z0-9]/.test(ch);

  while (left < right) {
    if (!isAlphaNumeric(s[left])) {
      left++;
    } else if (!isAlphaNumeric(s[right])) {
      right--;
    } else {
      if (s[left].toLowerCase() !== s[right].toLowerCase()) {
        return false;
      }

      left++;
      right--;
    }
  }

  return true;
}

Complexity

How to Explain It in an Interview