0125.Valid Palindrome

• Link: 125. Valid Palindrome - Easy
• Track: NeetCode150

Question

Example 1:

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

Restate the problem

Palindrome: reads the same forwards and backwards

• Given a string s
• Determine whether it is Palindrome
• Only consider alphanumeric characters (letters and digits)
• Ignore letter case (uppercase and lowercase)
• Return True if correct

Edge Case

• "", return True

---

Method	Approach	Time Complexity	Space Complexity
Method 1 ⭐	Two Pointers	$O(n)$	O(1)
Method 2	Slicing	$O(n)$	$O(n)$

Method 1 - Two Pointers

Approach

• Use two pointers: left = 0, right = len(s) - 1
• While left < right:
  • Move left forward until it points to an alphanumeric character (s[left].isalnum())
  • Move right backward until it points to an alphanumeric character
  • Compare s[left].lower() and s[right].lower() (ignore case)
    • If they are different → return False
  • If they match, move both pointers inward: left += 1, right -= 1
• If all valid character pairs match, return True

Complexity

• Time Complexity: $O(n)$
• Space Complexity: $O(1)$

Code

class Solution:
    def isPalindrome(self, s: str) -> bool:
        left = 0
        right = len(s) - 1
        while left < right: # length is odd, not compare the middle
            while left < right and not s[left].isalnum():
                left += 1
 
            while left < right and not s[right].isalnum():
                right -= 1
            
            if s[left].lower() != s[right].lower():
                return False
            else:
                left += 1
                right -= 1
        
        return True

Method 2 - Slicing

Approach

• Iterate through s and collect only alphanumeric characters, converting each to lowercase.
• Create a reversed copy using slicing: t[::-1].
• Return whether t equals its reverse.

Complexity

• Time Complexity: $O(n)$
• Space Complexity: $O(n)$

Code

class Solution:
    def isPalindrome(self, s: str) -> bool:
        # t = "".join(c.lower() for c in s if c.isalnum())
        # return t == t[::-1]
        s_list = []
        for c in s:
            if c.isalnum():
                s_list.append(c.lower())
        
        return s_list == s_list[::-1]

---

Common Mistake

• s.isalnum()
• s.lower()
• [::-1] works for both lists and strings, but it creates a reversed copy