Valid Palindrome

Problem

Given a string s, decide whether it is a palindrome under a relaxed reading: first imagine converting every uppercase letter to lowercase and deleting every character that is not a letter or a digit; s is a valid palindrome if what remains reads the same forwards and backwards. Return True or False.

An empty remainder (e.g. a string of only punctuation and spaces) counts as a palindrome.

Examples

• s = "A man, a plan, a canal: Panama" → True After cleaning: "amanaplanacanalpanama", which reads the same both ways.
• s = "race a car" → False Cleaned: "raceacar" — reversed it is "racaecar", not equal.
• s = " " → True Cleaning removes everything; the empty string is a palindrome by definition.
• s = "0P" → False Digits count: cleaned is "0p", and "0" != "p".

Constraints

• 1 <= s.length <= 2 * 10^5
• s consists of printable ASCII characters.
• Expected O(n) time; the follow-up asks for O(1) extra space (no cleaned copy).

Think about it first

TL;DR

Converging two pointers that skip non-alphanumerics — O(n) time, O(1) extra space.

Approach 1 — Brute force: clean, then compare with the reverse

Code the definition literally: build the filtered lowercase string and check it equals its reversal.

class Solution:
    def isPalindrome(self, s: str) -> bool:
        cleaned = [c.lower() for c in s if c.isalnum()]
        return cleaned == cleaned[::-1]

• Time: O(n) — one filtering pass plus one reversal/comparison pass.
• Space: O(n) for the cleaned copy (and its reverse).

The constraints don’t kill it — 2 * 10^5 characters at linear time is trivial. What it fails is the follow-up: O(1) extra space means no cleaned copy, which is exactly what the two-pointer version delivers (and what interviewers are fishing for).

Approach 2 — Converging two pointers, skip as you go

The insight: you never need the cleaned string — you only need its first-vs-last character comparisons, and those can be made directly on s by having each pointer skip the characters that cleaning would delete. Filtering and comparing fuse into one pass with no allocation.

class Solution:
    def isPalindrome(self, s: str) -> bool:
        left, right = 0, len(s) - 1
        while left < right:
            if not s[left].isalnum():
                left += 1
            elif not s[right].isalnum():
                right -= 1
            else:
                if s[left].lower() != s[right].lower():
                    return False
                left += 1
                right -= 1
        return True

Walkthrough on s = "A man, a plan, a canal: Panama" (first few steps):

…and so on until left >= right with no mismatch → True.

On s = "0P": both alphanumeric, "0" != "p" → False immediately.

• Time: O(n) — every iteration moves at least one pointer, so at most n iterations.
• Space: O(1) — two indices, no copies.

Structurally this is the same converging-pointer skeleton as in-place array reversal; the “skip invalid, act on valid” refinement is shared with Reverse Vowels of a String.

Approach 3 — Regex clean + slicing one-liner

The insight: the same clean-and-compare of Approach 1, expressed with a regular expression — worth knowing as the idiomatic quick form when O(1) space isn’t demanded. re.sub deletes everything outside a character class in one call.

import re


class Solution:
    def isPalindrome(self, s: str) -> bool:
        cleaned = re.sub(r"[^a-z0-9]", "", s.lower())
        return cleaned == cleaned[::-1]

Walkthrough on s = "race a car": lowercase is "race a car", the regex strips spaces → "raceacar"; its reverse is "racaecar", unequal at index 3 (e vs a) → False.

• Time: O(n).
• Space: O(n).

Common pitfalls

• Forgetting that digits are kept — "0P" is the classic trap test; alphanumeric means letters and digits, and .lower() on a digit is a harmless no-op.
• Comparing without normalizing case (or lowercasing only one side).
• Skipping non-alphanumerics with unguarded inner while loops — on a string like "!!" the pointers can run past each other or off the ends; re-checking left < right each iteration (as above) avoids it.
• Treating the empty cleaned string as False — by definition it’s a palindrome, and the loop above naturally returns True for it.

Pattern takeaway

Symmetric string/array predicates (“reads the same from both ends”) are the home turf of converging two pointers: compare the outermost meaningful pair, move inward, and fail fast on the first mismatch. When some positions don’t count, skip them inside the same loop rather than pre-filtering — fusing the filter into the scan is what turns O(n) extra space into O(1), and the identical skeleton extends to Valid Palindrome II (one deletion allowed) by branching once on the first mismatch.