Valid Palindrome

A phrase is a palindrome if, after converting all uppercase letters to lowercase and removing every character that is not a letter or digit, it reads the same forwards and backwards. Given a string s, return true if it is a palindrome.

Examples

Input:  s = "A man, a plan, a canal: Panama"
Output: true      ("amanaplanacanalpanama")

Input:  s = "race a car"
Output: false     ("raceacar")

Input:  s = " "
Output: true      (empty after cleaning)

Constraints

• 1 ≤ s.length ≤ 2 × 10⁵, printable ASCII characters.

Explanation

Brute force — build a cleaned copy, O(n) extra space

Keep only alphanumeric characters, lowercase them, and compare the result with its reverse. Simple and fine in most interviews.

Optimal — two pointers, O(1) extra space

Put left at the start and right at the end. Skip characters that aren’t letters or digits on each side, then compare the two characters case-insensitively. If they differ, it isn’t a palindrome; otherwise move both pointers inward. Stop when they meet.

Complexity

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