Valid Palindrome

Given a string s, return true if it is a palindrome, otherwise return false.

A palindrome is a string that reads the same forward and backward. It is also case-insensitive and ignores all non-alphanumeric characters.

Note: Alphanumeric characters consist of letters (A-Z, a-z) and numbers (0-9).

After considering only alphanumerical characters we have "wasitacaroracatisaw", which is a palindrome.

"tabacat" is not a palindrome.

Approach

Use two pointers at the ends of the string. Move each pointer inward until it points to an alphanumeric character, then compare their lowercase forms. If any pair differs, return false; if the pointers cross, the string is a valid palindrome. This handles inputs with only spaces/punctuation and mixed case.

Why It Works

Ignoring non-alphanumeric characters and case, a palindrome reads the same forward and backward. The two-pointer scan compares the characters in mirrored positions of this filtered view. Any mismatch proves the string is not a palindrome; if all mirrored pairs match, it is.

Complexity

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

Reference Implementation (Python)

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():
                left += 1
            while left < right and not s[right].isalnum():
                right -= 1
            if s[left].lower() != s[right].lower():
                return False
            left += 1
            right -= 1
        return True