Leetcode - Valid Palindrome Solution

Checking if a string reads the same forward and backward seems like a simple problem. My first instinct was to reverse the string and compare, but that approach creates a new string and uses O(n) extra space. There's a better way that uses O(1) space: the two pointers technique.

The key insight is that we don't need to reverse anything. We can check from both ends simultaneously, moving inward until we either find a mismatch or confirm it's a palindrome.

Understanding the Problem

Given a string, determine if it reads the same forward and backward. "racecar" is a palindrome, "hello" is not. The challenge is doing this efficiently without using extra space.

My First Approach

My initial solution was straightforward: reverse the string and compare.

function isPalindromeNaive(s) {
  const reversed = s.split("").reverse().join("");
  return s === reversed;
}

This works, but it creates a new string which uses O(n) extra space. For large strings, this isn't ideal. I knew there had to be a better way.

The Two Pointers Insight

The breakthrough came when I realized I don't need to reverse anything. I can check from both ends simultaneously, moving inward until I find a mismatch or confirm it's a palindrome.

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

The Solution

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

  while (left < right) {
    // If characters don't match, it's not a palindrome
    if (s[left] !== s[right]) {
      return false;
    }

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

  return true; // All characters matched!
}

How It Works

Let me trace through "racecar" step by step:

• 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 new string created
• Only using two integer variables for pointers

Time Complexity: O(n)

• Single pass through the string
• Each character is checked at most once
• 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. Case sensitivity: The problem might require case-insensitive comparison (this solution assumes case-sensitive)

Key Takeaways

• 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 - optimal for this problem
• This pattern appears in many string and array problems

The two pointers technique has become one of my go-to tools for problems involving symmetry or relationships between opposite ends of a sequence. Once you see the pattern, you'll start recognizing opportunities to use it everywhere.