Valid Palindrome

Problem

Given a string s, first convert all uppercase letters to lowercase and remove every character that is not a letter or a digit. Return True if the result reads the same forwards and backwards, and False otherwise.

An empty result (for example, 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.

def isPalindrome(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).

This handles the constraints fine: 2 * 10^5 characters at linear time is fast. It fails only the follow-up, which asks for O(1) extra space and therefore no cleaned copy. The two-pointer version below meets that requirement.

Approach 2 — Converging two pointers, skip as you go

You never need to build 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 then happen in one pass with no allocation.

def isPalindrome(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.

This is the same converging-pointer structure 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 same clean-and-compare as Approach 1, expressed with a regular expression. It is a concise form to know when O(1) space is not required. re.sub deletes everything outside a character class in one call.

import re


def isPalindrome(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: alphanumeric means letters and digits, and .lower() on a digit is a 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) prevents it.
• Treating the empty cleaned string as False. By definition it is a palindrome, and the loop above returns True for it.

Pattern takeaway

Symmetric string and array predicates (“reads the same from both ends”) suit converging two pointers: compare the outermost meaningful pair, move inward, and fail 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). The same structure extends to Valid Palindrome II (one deletion allowed) by branching once on the first mismatch.