LeetCode: Valid Palindrome

Problem:

https://leetcode.com/problems/valid-palindrome/description/

Code:

class Solution:
    def isPalindrome(self, s: str) -> bool:
        left, right = 0, len(s)-1
        while left<right:
            while left<right and not s[left].isalnum(): # until a valid character, also (l<r)
                left+=1

            while left<right and not s[right].isalnum(): #until a valid character, also (l<r)
                right-=1

            if s[left].lower() != s[right].lower():
                return False
            left+=1
            right-=1
        return True

Key Points:

Problem in Simple Words

Check if a string reads the same forwards and backwards, ignoring:

• spaces

• punctuation

• capitalization
  Only letters and digits matter.

---

Core Idea (Two-Pointers, In-Place Check)

We use two pointers:

• left starts at the beginning

• right starts at the end

We move them toward each other, comparing characters as we go.

---

Handling Non-Alphanumeric Characters

If a character is not a letter or number:

• Skip it

• Do not compare it
  This handles cases like "A man, a plan, a canal: Panama" correctly.

---

When We Compare Values

Once both pointers land on valid characters:

• Convert to lowercase and check if they match

• If mismatch → not a palindrome → return False

If they match:

• Move both pointers inward and keep checking

---

Why This Approach Is Good

• Does not create a new cleaned string

• Skips unwanted characters on the fly

• Uses the original string → true O(1) extra space

---

When We Stop

If pointers cross each other:

• All compared characters matched → return True

---

Complexity

• Time: O(n) → every char visited at most once

• Space: O(1) → only two pointer variables used