Marauder Bot

Problem

You are given a string that may contain letters, digits, spaces, and punctuation. Ignoring case and ignoring every character that is not a letter or digit, decide whether what remains reads identically forwards and backwards.

Example. "A man, a plan, a canal: Panama" is a palindrome once you drop the spaces and punctuation and lowercase everything, leaving "amanaplanacanalpanama". "race a car" is not, since "raceacar" does not mirror itself.

Key idea

The direct approach builds a cleaned-up copy of the string (lowercased, with punctuation and spaces stripped), then compares it to its own reverse. That works, but it allocates a second string and scans the input twice.

A leaner approach uses two pointers, one starting at the front of the original string and one at the back, moving toward each other. At each step, advance the front pointer past any character that is not a letter or digit, and do the same for the back pointer moving backward. Once both pointers rest on alphanumeric characters, compare them case-insensitively; if they differ, the string is not a palindrome. If they match, step both pointers inward and repeat. The check succeeds once the pointers meet or cross, having never found a mismatch. This avoids building any new string: every decision is made by indexing directly into the original.

Solution

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

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

  while (left < right) {
    // Skip non-alphanumeric characters independently on each side.
    while (left < right && !isAlphanumeric(s[left])) {
      left++;
    }
    while (left < right && !isAlphanumeric(s[right])) {
      right--;
    }

    // Compare case-insensitively, not by raw equality.
    if (s[left].toLowerCase() !== s[right].toLowerCase()) {
      return false;
    }

    left++;
    right--;
  }

  return true;
}

Complexity

Time: O(n). Each pointer visits every character at most once.
Space: O(1). No auxiliary string or buffer is built.

Watch out for

Skipping non-alphanumeric characters must happen independently on both sides before each comparison, not just once.
Comparing characters needs a case-insensitive check, not a raw equality check.
An empty string, or a string with no alphanumeric characters at all, should count as a palindrome by default.

Pattern

This is the two-pointer convergence pattern applied to a symmetry check: walk inward from both ends and stop at the first contradiction. The same shape (advance two indices toward the middle while a local condition holds) reappears in reversing arrays in place and in other palindrome-style verification problems.

Valid Palindrome