Frontend Beauty
ESC

Type to search the knowledge base.

Valid Palindrome

Alphanumeric palindrome check — two pointers skipping non-alphanumerics, O(n) time O(1) space.

beginner3 min read
  • dsa
  • strings
  • interview
  • Google
  • Meta
  • Amazon

The problem

After converting to lowercase and removing non-alphanumeric characters, does s read the same forward and backward?

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

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

Input:  s = " "
Output: true

Brute force

Filter + reverse string compare.

function isPalindromeBrute(s: string): boolean {
  const cleaned = s.toLowerCase().replace(/[^a-z0-9]/g, "");
  return cleaned === [...cleaned].reverse().join("");
}
Time O(n)
Space O(n)

Optimal: two pointers

function isPalindrome(s: string): boolean {
  let lo = 0;
  let hi = s.length - 1;

  const isAlnum = (ch: string) => /[a-z0-9]/i.test(ch);

  while (lo < hi) {
    while (lo < hi && !isAlnum(s[lo])) lo++;
    while (lo < hi && !isAlnum(s[hi])) hi--;
    if (s[lo].toLowerCase() !== s[hi].toLowerCase()) return false;
    lo++;
    hi--;
  }
  return true;
}

Char-code version of alnum avoids regex if you prefer:

function isAlnumCode(ch: string): boolean {
  const c = ch.charCodeAt(0);
  return (
    (c >= 48 && c <= 57) ||
    (c >= 65 && c <= 90) ||
    (c >= 97 && c <= 122)
  );
}
Time O(n)
Space O(1)

Edge cases

  • Empty / only punctuation → true
  • Single character
  • Numbers mixed with letters
  • Unicode letters — LC usually ASCII

Common bugs

  • Forgetting to lowercase
  • Treating underscore as alnum
  • Moving lo/hi past each other incorrectly
  • Off-by-one when skipping

Interview delivery

  1. Define cleaned palindrome.
  2. Two pointers skip junk.
  3. Compare lowercased.
  4. O(n)/O(1).
  5. Follow-up: valid palindrome II (one delete).

Walkthrough

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

  • lo at 'A', hi at 'a' — both alnum, equal ignoring case
  • skip spaces and punctuation as pointers move inward
  • eventually all letter pairs match → true

s = "race a car"

  • after clean mentally: raceacar
  • 'r' vs 'r' ok, … middle fails on 'e' vs 'a' → false

Why not always filter first?

Filtering builds a new string (clear code, O(n) space). Two pointers keep O(1) space and show you control index movement — the skill they reuse on linked-list and array problems. If the language makes toLowerCase allocate per char, mention that cost is still O(n) total characters examined.

  1. Valid Palindrome II — allow one deletion; branch when mismatch.
  2. Palindrome Linked List — reverse second half, compare.
  3. Longest Palindromic Substring — expand around centers.

Name one of these if they ask “what next?” after you finish early.

Further reading