Given a string s, decide whether it reads the same forwards and backwards once everything that is not a letter or a digit is ignored and case is flattened. "A man, a plan, a canal: Panama" qualifies; "race a car" does not. A string with nothing alphanumeric left counts as a palindrome.
Examples
Example 1:
Input: s = "A man, a plan, a canal: Panama"
Output: true
Explanation: stripped and lowered it reads "amanaplanacanalpanama".
Example 2:
Input: s = "race a car"
Output: false
Example 3:
Input: s = "0P"
Output: false
Explanation: digits count as alphanumeric, and '0' is not 'p'.
Example 4:
Input: s = " "
Output: true
Constraints
1 <= s.length <= 2 * 10^5
s consists of printable ASCII characters.
Prerequisites
Two pointers — one pass with an index at each end, and the argument for why moving one of them cannot lose the answer.
How to think about it
1. Clean, Then Compare
Intuition
Strip out everything that is not a letter or digit, lower the case, and ask whether the result reads the same backwards. It is the definition made literal, and worth writing before optimising — it is also the version that fits in one line of Python.
Algorithm
1. Build a cleaned string of the alphanumeric characters, lowercased. 2. Compare it to its reverse.
Time & Space
Time O(n). Space O(n) for the cleaned copy — which is the only thing the two-pointer version improves.
2. Two Pointers In Place Optimal
Intuition
The copy is avoidable: compare the ends directly and walk inward, skipping anything that is not alphanumeric as you go. Same answer, no second string — and the skipping-inside-the-loop is what interviewers are actually watching you write.
Algorithm
1. Put one pointer at each end. 2. Advance each past characters that are not letters or digits. 3. Compare the two, case-insensitively; a mismatch is false. 4. Step both inward; pointers crossing means it is a palindrome.
Time & Space
Time O(n) — each pointer moves forward only. Space O(1).