Two Pointers

Try It Yourself

Use the editor below to solve the problem before reading the solution. Start one pointer at the beginning of the string and another at the end. Decide how each pointer should move when it reaches a character that is not a letter or digit, and return false as soon as the two meaningful characters do not match.

Submit your implementation when it passes the examples. A complete submission also needs to handle capitalization, punctuation, numbers, and a single-character string.

Solution

The two-pointers approach compares the next meaningful character from each end of the string. The left pointer moves forward and the right pointer moves backward. Before comparing characters, each pointer skips anything that is not a letter or digit.

When both pointers reach valid characters, compare their lowercase forms. A mismatch means the string cannot be a palindrome. If they match, move both pointers inward and repeat until they meet.

function isAlphaNumeric(character) {
  const code = character.charCodeAt(0);

  const isDigit = code >= 48 && code <= 57;
  const isUppercaseLetter = code >= 65 && code <= 90;
  const isLowercaseLetter = code >= 97 && code <= 122;

  return isDigit || isUppercaseLetter || isLowercaseLetter;
}

function isPalindrome(s) {
  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;
}

Big O notation