RezloRezloPrep
Sign Up Free
Two Pointer PatternLeetCode 125

Valid Palindrome

7 min read•Easy•In-Place Skip Variant
Check whether a string is a palindrome after normalizing it - without ever building the normalized string - by skipping non-alphanumeric characters directly on two pointers walking inward.

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.

code
Input:  s = "A man, a plan, a canal: Panama"
Output: true
// normalized: "amanaplanacanalpanama"

Input:  s = "race a car"
Output: false
// normalized: "raceacar"

Input:  s = " "
Output: true
// normalized: ""

Approach: Two Pointers, Skip In Place

The obvious first move is to build a cleaned-up string - strip everything that isn't alphanumeric, lowercase what's left, then check it against its own reverse. That works, but it costs O(n) extra space for the copy.

The fix follows the same Reverse String skeleton this whole module is built on: walk two pointers inward from both ends of the original string, and instead of always swapping, skip over anything that isn't alphanumeric before comparing.

left skips forward over non-alphanumeric characters

If s[left] isn't a letter or digit, advance left without comparing it to anything yet.

right skips backward over non-alphanumeric characters

Same idea from the other end: if s[right] isn't a letter or digit, pull right inward without comparing.

Only once both pointers are parked on alphanumeric characters do you compare them, case-insensitively. A mismatch means the answer is immediately false; a match means both pointers move one step inward and the loop continues until they cross.

valid_palindrome.js
JavaScript
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;
}

console.log(isPalindrome("A man, a plan, a canal: Panama")); // true
console.log(isPalindrome("race a car")); // false

Complexity Analysis

Time Complexity: O(n)

Every character is visited at most once, whether it gets skipped or compared - left and right only ever move toward each other.

Space Complexity: O(1)

No cleaned copy of the string is ever built. The pointers read directly from the original string, so the only extra memory is the two index variables.

Common Mistake

Building a normalized string first (s.replace(/[^a-z0-9]/gi, "").toLowerCase()) and then reversing it to compare is a completely valid way to get the right answer, but it's O(n) extra space - worth naming out loud even if you lead with it, since the two-pointer version is the answer that's actually being tested for. A more common bug in the in-place version is using if/if instead of if/else if for the two skip checks, which can advance both pointers past a pair of characters that should have been compared.

How to Explain it in an Interview

The 30-Second Spoken Pitch
"I'll use two pointers, one starting from each end of the string. If either pointer is on a non-alphanumeric character, I'll skip it. Once both pointers point to valid characters, I'll compare them case-insensitively. If they don't match, the string cannot be a palindrome, so I return false. Otherwise, I move both pointers inward and continue. If the pointers meet without finding a mismatch, I return true."
If the Interviewer Probes Deeper:
Why compare with <= instead of < like Reverse String uses?

A single leftover character in the middle (odd-length normalized string) still needs to be evaluated by the skip checks so the pointers can finish converging correctly - <= lets left and right land on the same index one last time without that being treated as an error.

How would you handle an empty string, or one with no alphanumeric characters at all?

left and right just skip past every character without ever finding a pair to compare, left eventually exceeds right, the loop exits, and true is returned - matching the problem's rule that an empty normalized string counts as a palindrome.

Could you solve this recursively instead?

Yes, by recursing on (left + 1, right - 1) after skipping non-alphanumeric characters at each end, but that trades the O(1) space of the iterative version for O(n) call-stack space - worth mentioning as a tradeoff, not a better answer.

Next Topictest