Valid Palindrome

The problem. A phrase is a palindrome if, after turning every uppercase letter into lowercase and removing everything that isn't a letter or a digit, it reads the same forwards and backwards. Given a string s, return true if it is a palindrome.

Example

s = "No lemon, no melon"                ->  true
s = "A man, a plan, a canal: Panama"    ->  true
s = "race a car"                        ->  false   ("raceacar" backwards is "racaecar")
s = " "                                 ->  true    (nothing left: an empty string reads the same)

The idea: compare mirror pairs, skipping the noise

A palindrome's first character equals its last, its second equals its second-to-last, and so on — the two-pointer check. The only twist is the noise: spaces, commas and case. The obvious fix is to clean the string first. The better fix is to let each pointer skip the characters that don't count, so no cleaned copy is ever made.

1. Clean, reverse, compare

Build the cleaned lowercase string, then check it equals its own reverse.

1function isPalindrome(s) {2  const clean = s.toLowerCase().replace(/[^a-z0-9]/g, "");   // keep letters and digits only3  return clean === [...clean].reverse().join("");             // equal to its own reverse?4}

Time O(n), space O(n). Three passes — clean, reverse, compare — and two new strings as long as the input.

2. Two pointers that skip

Start at both ends. If the left character isn't a letter or digit, step past it; same on the right. When both point at real characters, compare them ignoring case: a mismatch means false, a match moves both inwards.

1function isPalindrome(s) {2  const ok = (ch) => /[a-z0-9]/i.test(ch);   // letters and digits count; the rest is skipped3  let left = 0, right = s.length - 1;4  while (left < right) {5    if (!ok(s[left])) { left++; continue; }   // skip spaces and punctuation6    if (!ok(s[right])) { right--; continue; }7    if (s[left].toLowerCase() !== s[right].toLowerCase()) return false;   // a mismatch8    left++;9    right--;10  }11  return true;12}

Time O(n), space O(1). Every step moves at least one pointer, so there are at most n steps, and only two indexes are stored.

Comparing the approaches

Approach 1 is quick to write and fine to start with; interviewers usually ask next for O(1) space, which is approach 2.

Edge cases to test

Variations