[LeetCode] 125. Valid Palindrome

Problem

LeetCode 125. Valid Palindrome

A phrase is a palindrome if, after converting all uppercase letters to lowercase and removing all non-alphanumeric characters, it reads the same forward and backward.

Input: s = "A man, a plan, a canal: Panama"
Output: true
Explanation: "amanaplanacanalpanama" is a palindrome.

---

Initial Thought (Failed)

Create a new string with only filtered characters and check if it equals its reverse.

• clean_s = [c.lower() for c in s if c.isalnum()]
• return clean_s == clean_s[::-1]

Is this bad? No, it works. But it requires $O(N)$ extra space to store the cleaned string. Can we do it with $O(1)$ space?

---

Key Insight

We can simply compare characters from the outside in using Two Pointers.

• left pointer starts at 0.
• right pointer starts at len(s) - 1.
• Skip non-alphanumeric characters.
• Stop if characters don’t match.

---

Step-by-Step Analysis

s = "a A"

graph TD
    S1["L=0 ('a'), R=2 ('A') <br> Match? Yes (case-insensitive)"] --> S2["Move both pointers to index 1 <br> (they meet)"]
    S2 --> S3["Pointers met <br> Loop ends"]
    S3 --> F[Return True]
    style F fill:#aaffaa

Let’s trace s = "A b A":

1. L at index 0 (‘A’), R at index 4 (‘A’). Match. Move L->1, R->3.
2. L at index 1 (space), R at index 3 (space). Skip both.
3. L at index 2 (‘b’), R at index 2 (‘b’). Match.
4. L == R (both at index 2), loop ends -> Success.

---

Solution

class Solution:
    def isPalindrome(self, s: str) -> bool:
        left, right = 0, len(s) - 1
        
        while left < right:
            # 1. Skip non-alphanumeric from left
            while left < right and not s[left].isalnum():
                left += 1
            # end while
            
            # 2. Skip non-alphanumeric from right
            while left < right and not s[right].isalnum():
                right -= 1
            # end while
            
            # 3. Compare (case-insensitive)
            if s[left].lower() != s[right].lower():
                return False
            # end if
            
            left += 1
            right -= 1
        # end while
        
        return True
    # end def

---

Complexity

• Time Complexity: $O(N)$
  • We iterate through the string at most once.
• Space Complexity: $O(1)$
  • We only use two integer variables. No extra string creation.

---

Key Takeaways

Point	Description
Two Pointers	Standard technique for meeting-in-the-middle or comparing ends
In-Place	Avoiding extra memory allocation is a key optimization
Handling Noise	Skipping invalid characters allows checking logic to remain clean