Valid Palindrome

Problem

Given a string s, return true if it is a palindrome, or false otherwise.

You must ignore non-alphanumeric characters and treat uppercase and lowercase letters as equivalent.

Intuition

A palindrome reads the same from the left and the right. That symmetry is exactly what two pointers are good at.

The only complication is the filtering rule. We cannot compare every character directly because punctuation and spaces are ignored, and letters are case-insensitive. So the pointers must first skip over irrelevant characters, then compare the normalized values.

This is the canonical "converging pointers" pattern: start at both ends, move inward, and stop immediately when a mismatch appears.

Approach

impl Solution {
    pub fn is_palindrome(s: String) -> bool {
        let bytes = s.as_bytes();
        let mut left = 0usize;
        let mut right = bytes.len().saturating_sub(1);

        while left < right {
            while left < right && !bytes[left].is_ascii_alphanumeric() {
                left += 1;
            }
            while left < right && !bytes[right].is_ascii_alphanumeric() {
                right -= 1;
            }

            if bytes[left].to_ascii_lowercase() != bytes[right].to_ascii_lowercase() {
                return false;
            }

            left += 1;
            right -= 1;
        }

        true
    }
}

function isPalindrome(s: string): boolean {
  const isAlphaNum = (code: number): boolean =>
    (code >= 48 && code <= 57) ||
    (code >= 65 && code <= 90) ||
    (code >= 97 && code <= 122);

  let left = 0;
  let right = s.length - 1;

  while (left < right) {
    while (left < right && !isAlphaNum(s.charCodeAt(left))) left++;
    while (left < right && !isAlphaNum(s.charCodeAt(right))) right--;

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

    left++;
    right--;
  }

  return true;
}

Trace

For s = "A man, a plan, a canal: Panama":

The important part is not each character, but that the pointers only move inward.

Edge cases

• Empty string is a palindrome.
• Only punctuation is also a palindrome after filtering.
• Single alphanumeric character is trivially a palindrome.
• Mixed case should normalize before comparison.

Takeaway

Two pointers are a symmetry tool.

When the correctness condition depends on the ends of a sequence matching each other, you can often solve the problem in one pass by converging from both sides and skipping anything irrelevant along the way.