Valid Palindrome

Problem

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. Alphanumeric characters include letters and numbers.

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

Example 1:

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

Example 2:

Input: s = "race a car"
Output: false
Explanation: "raceacar" is not a palindrome.

Example 3:

Input: s = " "
Output: true
Explanation: s is an empty string "" after removing non-alphanumeric characters.
Since an empty string reads the same forward and backward, it is a palindrome.

Constraints:

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

Solution

Approach: Two Pointers

The key insight is to use two pointers starting from both ends of the string, moving inward while skipping non-alphanumeric characters. We compare characters (case-insensitive) at each pointer position. If all matching characters are equal, the string is a palindrome.

This approach is efficient because it only requires one pass through the string with O(1) extra space.

Implementation

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

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

            # Skip non-alphanumeric characters from right
            while left < right and not s[right].isalnum():
                right -= 1

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

            left += 1
            right -= 1

        return True

Alternative (Filter and Reverse):

class Solution:
    def isPalindrome(self, s: str) -> bool:
        # Filter alphanumeric characters and convert to lowercase
        filtered = ''.join(c.lower() for c in s if c.isalnum())

        # Check if filtered string equals its reverse
        return filtered == filtered[::-1]

Complexity Analysis

Time Complexity: O(n), where n is the length of the string. We visit each character at most once with the two-pointer approach.
Space Complexity: O(1) for the two-pointer approach. The alternative approach uses O(n) space for the filtered string.

Key Insights

Two Pointers Pattern: Using pointers from both ends is more efficient than creating a filtered string. We can skip invalid characters in-place without allocating extra space.
Skip Non-Alphanumeric: The nested while loops efficiently skip over characters we don’t care about, allowing us to only compare valid characters.
Case-Insensitive Comparison: Using .lower() handles the case-insensitive requirement. We could also use .upper() - the choice doesn’t matter.
Early Termination: As soon as we find a mismatch, we can immediately return false without checking the rest of the string.
Edge Cases: Empty strings and strings with only non-alphanumeric characters are considered palindromes by definition (they become empty after filtering).