A palindrome is a sequence of characters that reads the same forwards and backwards. Given a string s, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

For example:

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

Constraints:

  • 1 <= s.length <= 2 * 10^5
  • s consists only of printable ASCII characters.

Solution

Approach:

  • Two Pointers: Initialize two pointers, left at the beginning of the string and right at the end.
  • Skip Non-Alphanumeric: While left is less than right:
    • Move left forward until it points to an alphanumeric character.
    • Move right backward until it points to an alphanumeric character.
  • Compare (Case-Insensitive): If both pointers are valid (left < right):
    • Compare the characters at s[left] and s[right] after converting them to lowercase.
    • If they do not match, the string is not a palindrome; return false.
  • Advance Pointers: If they match, move left one step forward and right one step backward.
  • Result: If the loop completes without finding any mismatches, the string is a palindrome; return true.

This approach efficiently checks the string in-place without creating a new string, optimizing space complexity.

class Solution:
    def isPalindrome(self, s: str) -> bool:
        left, right = 0, len(s) - 1

        while left < right:
            # Move left pointer past non-alphanumeric characters
            while left < right and not s[left].isalnum():
                left += 1
            # Move right pointer past non-alphanumeric characters
            while left < right and not s[right].isalnum():
                right -= 1

            # Compare characters (case-insensitive)
            if s[left].lower() != s[right].lower():
                return False

            # Move pointers inward
            left += 1
            right -= 1

        return True