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.

Input: "A man, a plan, a canal: Panama" → true
Input: "race a car"                     → false
Input: " "                              → true

Solution

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 "race a car": r/r match, a/a match, c/c match, then the left side reaches e while the right skips the space to land on a - e != a, so it returns False. The skipping handles the embedded space without any pre-filtering pass.

Edge cases: an empty string or one made only of punctuation returns True because the pointers cross before any comparison runs; "0P" 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.