Leetcode - Valid Palindrome Solution

A palindrome reads the same forward and backward. My first instinct was to reverse the string and compare, but that approach creates a new string and uses O(n) extra space. There is a better way that uses O(1) space: the two pointers technique.

The algorithm can compare characters at opposite ends directly. It moves inward until a mismatch occurs or the pointers meet.

Understanding the Problem

LeetCode 125 uses printable ASCII input. Ignore punctuation and spaces, and compare letters without case differences. Digits remain part of the comparison. For example, "A man, a plan, a canal: Panama" is valid, while "race a car" is not.

My First Approach

The first version removes nonalphanumeric characters and converts letters to lowercase. It then reverses the result and compares both strings:

function isPalindromeNaive(s) {
  const normalized = s.toLowerCase().replace(/[^a-z0-9]/g, "");
  const reversed = normalized.split("").reverse().join("");
  return normalized === reversed;
}

The normalized and reversed strings use O(n) extra space. The two pointer version checks the original input directly.

The Two Pointers Insight

The two pointer approach checks both ends simultaneously, moving inward until it finds a mismatch or confirms a palindrome.

The two pointers technique works here because palindromes are symmetric. If the characters at both ends match, I can move inward and check the next pair. If they do not match, I know it is not a palindrome.

Two pointer implementation

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

  while (left < right) {
    // Skip characters that the problem excludes from comparison.
    while (left < right && !/[a-z0-9]/i.test(s[left])) left++;
    while (left < right && !/[a-z0-9]/i.test(s[right])) right--;
    if (left >= right) break;

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

    // Move both pointers inward
    left++;
    right--;
  }

  return true; // All characters matched!
}

Pointer trace

For "racecar", the pointers move as follows:

• Initial: left=0 ('r'), right=6 ('r')
• Characters match, so move inward: left=1, right=5
• left=1 ('a'), right=5 ('a'): match! Move inward: left=2, right=4
• left=2 ('c'), right=4 ('c'): match! Move inward: left=3, right=3
• left >= right, exit loop
• Return true!

Why This Approach Is Better

Space Complexity: O(1)

• No normalized copy of the full input is created
• Only using two integer variables for pointers

Time Complexity: O(n)

• Single pass through the string
• Each pointer moves in one direction, so the total work is O(n)
• Potentially faster than reversing because we can exit early if we find a mismatch

Simplicity

• The logic is straightforward and easy to understand
• No complex string operations needed

Common Pitfalls

When implementing this, watch out for:

1. Off by one errors: Make sure your loop condition is left < right (not <=) to avoid checking the middle character twice
2. Edge cases: Empty strings and single character strings are palindromes by definition
3. Input rules: Ignore punctuation and spaces. Compare letters without case differences, and retain digits.

Palindrome summary

• Two pointers from both ends is perfect for symmetric problems like palindromes
• No need to reverse when you can check directly
• O(n) time, O(1) space. This is optimal for this problem
• This pattern appears in many string and array problems

The two pointers technique is useful for problems involving symmetry or relationships between opposite ends of a sequence.