A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Given a string s, return true if it is a palindrome, or false otherwise.

  • Input: A string s.
  • Output: true if s is a palindrome, false otherwise.
  • Constraints:
    • 1 <= s.length <= 2 * 10^5
    • s consists only of printable ASCII characters.
  • Example:
    Input: s = "A man, a plan, a canal: Panama"
Output: true
Explanation: "amanaplanacanalpanama" is a palindrome.

Solution

The most efficient way to check for a palindrome is using a two-pointer approach.

  • Preprocessing: First, create a new string or process the original string such that only alphanumeric characters remain and all characters are converted to lowercase. This simplifies comparison.
  • Two Pointers: Initialize two pointers, left at the beginning and right at the end of the processed string.
  • Comparison: Move left forward and right backward, comparing characters at each position.
    • If processed_string[left] is not equal to processed_string[right] at any point, the string is not a palindrome, so return false.
    • Continue this process until left crosses right.
  • Result: If the loop completes without finding any mismatches, the string is a palindrome, so return true.
class Solution:
    def isPalindrome(self, s: str) -> bool:
        # Preprocess the string: convert to lowercase and remove non-alphanumeric characters
        # Using a list comprehension for clarity and performance
        filtered_chars = [char.lower() for char in s if char.isalnum()]
        processed_s = "".join(filtered_chars)

        # Use two pointers
        left, right = 0, len(processed_s) - 1

        while left < right:
            if processed_s[left] != processed_s[right]:
                return False
            left += 1
            right -= 1

        return True