Valid Palindrome

Problem Given a string, determine whether it is a palindrome — reads the same forwards and backwards. (Clarify the variant: raw comparison, or the LC-125 form that ignores case and non-alphanumeric characters.)

Input / Output

• Input: string s.
• Output: boolean.

Constraints

• |s| up to 2*10^5; O(n) time, O(1) space — no reversed-copy allocation in the ideal answer.

Example

• "A man, a plan, a canal: Panama" → true (alphanumeric, case-insensitive variant).
• "race a car" → false.

Expected approach

• Two pointers from both ends moving inward: skip non-alphanumeric characters (in the filtered variant), compare lowercased characters, fail fast on mismatch. O(n) time, O(1) space. Contrast with reverse-and-compare (O(n) space) and recursion (stack cost).