Valid Palindrome

Problem

Input validation systems often need to check whether a user-supplied string is a palindrome after stripping non-essential characters - useful in DNA sequence matching and username normalization. Given a string, return true if it is a palindrome considering only alphanumeric characters and ignoring case.

Example 1:

Input: "No lemon, no melon"
Output: true
Explanation: "nolemonnomelon" is a palindrome.

Example 2:

Input: "hello world"
Output: false
Explanation: "helloworld" is not a palindrome.

Example 3:

Input: ".,!"
Output: true
Explanation: after removing non-alphanumeric characters the string is empty, which reads the same forwards and backwards.

Constraints:

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

Solution Breakdown

Approach: converging two pointers with inline character normalization.

Start left at index 0 and right at the last index and walk them toward each other. Before every comparison, each pointer skips forward over any non-alphanumeric character: the inner while left < right and not s[left].isalnum() loop advances left past spaces and punctuation, and the symmetric loop pulls right inward. The left < right guard inside each inner loop is what keeps a pointer from running off the end when the remaining characters are all punctuation. Once both pointers sit on alphanumeric characters, compare them case-insensitively with .lower(); a mismatch immediately disproves the palindrome. On a match, step both inward and repeat. If the outer loop ends with the pointers having crossed, every alphanumeric pair matched and the string is a palindrome.

Trace "hello world": the very first comparison is h against d - h != d, so it returns False before any skipping is even needed. Contrast with "No lemon, no melon", where the pointers skip the comma and spaces and every pair matches.

Edge cases: an empty string or one made only of punctuation (like ".,") returns True because the pointers cross before any comparison runs; "9Z" returns False because normalization only folds case, not character class, so a digit never equals a letter.

Complexity: O(n) time, O(1) space - each character is visited at most once across both pointers and no filtered copy of the string is allocated.