valid-palindrome.ts

/**
 * 125. Valid Palindrome  (Easy)
 * Link: https://leetcode.com/problems/valid-palindrome/
 *
 * A phrase is a palindrome if, after lowercasing and removing all non
 * alphanumeric characters, it reads the same forward and backward. Return
 * whether `s` is a palindrome.
 *
 * Example:
 *   Input:  s = "A man, a plan, a canal: Panama"
 *   Output: true
 *
 * Approach:
 *   Two pointers from both ends move inward, skipping any non-alphanumeric
 *   characters, and compare the lowercased letters. A mismatch means not a
 *   palindrome. This avoids building a cleaned copy of the string.
 *
 * Time:  O(n)  — each pointer traverses at most the whole string once.
 * Space: O(1)  — comparison done in place.
 */
export function isPalindrome(s: string): boolean {
  let left = 0;
  let right = s.length - 1;

  while (left < right) {
    while (left < right && !isAlphaNumeric(s[left])) left++;
    while (left < right && !isAlphaNumeric(s[right])) right--;

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

  return true;
}

function isAlphaNumeric(ch: string): boolean {
  const code = ch.charCodeAt(0);
  return (
    (code >= 48 && code <= 57) || // 0-9
    (code >= 65 && code <= 90) || // A-Z
    (code >= 97 && code <= 122) // a-z
  );
}