Valid Palindrome

Problem

A palindrome is a string that reads the same forward and backward.

Given a string s, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

Examples of palindromes:

• "racecar"
• "A man, a plan, a canal: Panama"
• "Was it a car or a cat I saw?"

Implement the solution using:

1. Two-pointer technique (optimal)
2. String reversal comparison

Note: For this problem, empty strings are considered valid palindromes.

Constraints

• 1 ≤ s.length ≤ 2 × 10^5
• s consists only of printable ASCII characters
• Consider only alphanumeric characters (a-z, A-Z, 0-9)
• Ignore case (treat 'A' and 'a' as equal)

Examples

Example 1

Input:

s = "A man, a plan, a canal: Panama"

Output:

true

Explanation: After removing non-alphanumeric and lowercasing: "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: After removing non-alphanumeric: empty string, which is a palindrome.

Example 4

Input:

s = "Was it a car or a cat I saw?"

Output:

true

Explanation: "wasitacaroracatisaw" is a palindrome.

Function Signature

def is_palindrome(s: str) -> bool:
    """
    Check if the string is a valid palindrome.

    Args:
        s: Input string (may contain non-alphanumeric characters)

    Returns:
        True if s is a palindrome, False otherwise
    """
    pass

Estimated Time

15-20 minutes

Tags

two-pointers string easy classic interview