Valid Palindrome

After lowercasing and removing every non-alphanumeric character, decide whether a string reads the same forwards and backwards.

A way to picture it

Two friends start at opposite ends of a hallway lined with letters and walk toward each other, stepping over any furniture (spaces and punctuation). At every step they shout their letter. If they ever shout different letters, it's not a palindrome.

How to approach it

Two pointers from both ends: skip non-alphanumerics, compare case-insensitively, and move inward. No cleaned copy needed.

Example

Input: {"s":"A man, a plan, a canal: Panama"}. Output: true.

Complexity: O(n) time and O(1) space. Each pointer crosses the string at most once, in place.

This page includes an animated walkthrough, Java and Python solutions, and a question to check your understanding.