Valid Palindrome

Problem

Given a string s, return true if it is a palindrome, otherwise return false. A palindrome is a string that reads the same forward and backward. It is also case-insensitive and ignores all non-alphanumeric characters. (Alphanumeric characters are letters A-Z, a-z and digits 0-9.)

Example 1

Input:  s = "Was it a car or a cat I saw?"
Output: true

After keeping only alphanumerics and lowercasing: "wasitacaroracatisaw", a palindrome.

Example 2

Input:  s = "tab a cat"
Output: false

"tabacat" is not a palindrome.

Constraints

• 1 <= len(s) <= 1000
• s is made up of only printable ASCII characters.

Thinking

• Brute force idea: build a cleaned copy (alphanumerics only, lowercased), reverse it and compare → $O(n)$ time, but $O(n)$ extra space for the copy and its reverse.
• Key insight: a palindrome means s[i] matches s[n-1-i]. So compare from both ends inward with two pointers, skipping characters that don’t count. No copy needed → $O(1)$ space.
• Edge cases to remember: a string with no alphanumerics at all ("?!", " ") is a palindrome (the empty string); mixed case ("Aa"); digits count ("0P" is not a palindrome); the skip loops must also check left < right so they can’t run off the end.

Solution

Approach A — my solution (two pointers, skip non-alphanumerics) ✅ best practice

Complexity: Time $O(n)$ · Space $O(1)$

Already optimal: each pointer only moves inward, so every character is visited at most once, and nothing is copied. The inner while loops guard with left < right, so a string full of punctuation can’t push the pointers out of bounds.

def is_palindrome(s: str) -> bool:
    left = 0
    right = len(s) - 1

    while left < right:
        while left < right and not s[left].isalnum():
            left += 1
        while left < right and not s[right].isalnum():
            right -= 1
        if s[left].lower() != s[right].lower():
            return False
        left += 1
        right -= 1
    return True

Approach B — clean, then compare with the reverse (Pythonic)

Complexity: Time $O(n)$ · Space $O(n)$ (the cleaned string and its reversed copy)

The brute force from the hints. Shortest to write, and fast in practice because the work happens in C, but it uses extra memory, which is what the follow-up asks you to avoid.

def is_palindrome_reverse(s: str) -> bool:
    cleaned = "".join(c.lower() for c in s if c.isalnum())
    return cleaned == cleaned[::-1]

Scratch / Experiments

Worst case: a real palindrome (so neither approach can exit early) at the maximum length of 1000 characters, with punctuation and mixed case so the skipping and lowercasing do work.

Approach B is usually faster in wall-clock time despite the extra memory: its loop is a generator feeding str.join, and [::-1] and == run in C, while Approach A’s pointer loop runs line by line in Python. Same $O(n)$ time; A wins on space, which is the point of the question.

import random, string

half = "".join(random.choices(string.ascii_letters + string.digits + " ,.!?", k=500))
s = half + half[::-1].swapcase()  # mirror with flipped case: still a palindrome
assert is_palindrome(s) and is_palindrome_reverse(s)
%timeit is_palindrome(s)
%timeit is_palindrome_reverse(s)

Takeaways

• Pattern: “compare the start with the end” (palindromes, reversing in place, pair sums on a sorted array) → two pointers moving inward, $O(1)$ space. When some elements must be ignored, skip them with inner while loops that also check left < right.
• Mistakes I made: none in the algorithm, it’s the optimal solution. Things to keep doing: the bounds guard in the skip loops, and comparing .lower() on both sides instead of building a lowercase copy. (Note: str.isalnum() also accepts Unicode letters/digits like 'é' or '²'; fine here since the input is ASCII.)
• Related problems: Valid Palindrome II (#680, same two pointers, allow one deletion), Two Sum II (#167, two pointers on a sorted array), Reverse String (#344, swap from both ends), Longest Palindromic Substring (#5, expand from the center instead of shrinking from the ends), Palindrome Linked List (#234, no random access, so reverse the second half).