Topic: Learning notes

LeetCode 125: Valid Palindrome in TypeScript, From Cleaning to In-Place Two Pointers

Keep the submitted cleaned-string solution, then explain an in-place charCodeAt-based two-pointer alternative.

I first cleaned the string down to alphanumeric characters, then compared from both ends. That approach is direct and correct. Later I saw a version that skips punctuation in the original string, which made the difference clear. The two-pointer idea stays the same. The choice is whether to create another string first.

Problem

Original problem: LeetCode 125: Valid Palindrome

Given a string s, ignore non-alphanumeric characters and English letter case, then decide whether it is a palindrome. A palindrome reads the same from left to right and right to left.

A direct cleaned-string approach

This version does not enumerate all substrings or all character pairings, so its time is already linear. Its cost is the separate str, whose size grows with the input.

function isPalindromeAfterCleaning(s: string): boolean {
  if (s.length === 1) return true;

  const str = s.replace(/[^a-zA-Z0-9]/g, "").toLowerCase();
  let p1 = 0;
  let p2 = str.length - 1;

  while (p1 < p2) {
    if (str[p1] !== str[p2]) return false;

    p1 += 1;
    p2 -= 1;
  }

  return true;
}

replace() removes non-alphanumeric characters and toLowerCase() normalizes case. p1 then compares from the left while p2 compares from the right. A mismatch returns false immediately. If the pointers meet, the function returns true.

The loop compares at most str.length / 2 pairs, but asymptotic time is still O(n). Dividing by two does not change Big O. Cleaning and lowercasing also traverse the string, so total time is O(n). str is a new string, which makes auxiliary space O(n).

The one-character early return is unnecessary. An empty input or one that becomes empty after cleaning never enters the loop and naturally returns true.

An in-place two-pointer version I found later

The other version does not clean the full string first. Before each comparison, the left and right pointers skip characters that the problem says to ignore.

function isAlphanumeric(char: string): boolean {
  const lowerCase = char.toLowerCase();
  const code = lowerCase.charCodeAt(0);

  return (
    (code >= "a".charCodeAt(0) && code <= "z".charCodeAt(0)) ||
    (code >= "0".charCodeAt(0) && code <= "9".charCodeAt(0))
  );
}

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

  while (left < right) {
    while (left < right && !isAlphanumeric(s[left])) {
      left += 1;
    }

    while (left < right && !isAlphanumeric(s[right])) {
      right -= 1;
    }

    if (s[left].toLowerCase() !== s[right].toLowerCase()) {
      return false;
    }

    left += 1;
    right -= 1;
  }

  return true;
}

isAlphanumeric() only makes the membership rule explicit. It lowercases one character, then uses charCodeAt(0) to check the ranges a through z and 0 through 9. This is not a two-pointer formula to memorize. It is one way to test English letters and digits without using a regular expression.

I store the repeated charCodeAt(0) result in code so the condition is easier to read. This check relies on the problem’s enumerable English letters and digits. A requirement for all Unicode letters would need a different membership rule.

The pointers skip punctuation before comparing the case-insensitive forms of the remaining characters. Each pointer only advances toward the center, so each character is checked a fixed number of times. Time is O(n) and auxiliary space is O(1) because the function keeps only indexes and temporary character values.

Why the in-place version is correct

Before each actual comparison, left and right point to the outermost alphanumeric characters in the unprocessed interval. The inner loops skip only characters that the problem tells us to ignore, so they do not discard a character that needs comparison.

If the lowercase forms differ, no ignored character can remove that difference, so the string is not a palindrome. If they match, the pair can be removed and the same question remains for the smaller interval. If the pointers meet without a mismatch, the string is a palindrome.

Minimal verification

import assert from "node:assert/strict";

assert.strictEqual(isPalindrome("A man, a plan, a canal: Panama"), true);
assert.strictEqual(isPalindrome("race a car"), false);
assert.strictEqual(isPalindrome(" "), true);
assert.strictEqual(isPalindrome("0P"), false);
assert.strictEqual(isPalindrome("a."), true);

" " checks the result when every character is ignored. "0P" confirms that digits and letters still participate in comparison.

Common mistakes

• Treat O(n / 2) as a different Big O. It is still O(n).
• Call the cleaned-string version O(1) space. The new str takes O(n) space.
• Use \w to identify alphanumeric characters. It also accepts underscores, which are outside this problem’s definition.
• Compare before lowercasing and incorrectly reject "A" and "a".
• Skip punctuation without checking left < right again, which makes index handling harder to read.

Transferable idea

Two-pointer code does not always need to transform the whole input first. When a rule affects only some characters, skip them while the pointers move. This saves extra memory and keeps the comparison rule in one loop.

References

• LeetCode 125: Valid Palindrome
• MDN: String.prototype.charCodeAt()
• MDN: String.prototype.toLowerCase()
• Node.js: assert.strictEqual()