Valid Palindrome: Check a Phrase While Ignoring Case and Punctuation

Problem

Given a string, decide whether it is a palindrome once you keep only letters and digits and treat uppercase and lowercase as equal. An empty result counts as a palindrome. This is widely known as LeetCode 125, Valid Palindrome.

Assume printable ASCII input up to about 2 × 10^5 characters.

Examples

"Step on no pets!"   ->  True     (cleaned: "steponnopets")
"Data, a tad!"       ->  True     (cleaned: "dataatad")
"Lazy data"          ->  False    (cleaned: "lazydata")
"  ,."               ->  True     (nothing left)
"0P"                 ->  False    (the digit 0 is not the letter p)

Approach 1: brute force

Build the cleaned, lowercased string and compare it with its reverse.

def is_palindrome_copy(s):
    cleaned = [ch.lower() for ch in s if ch.isalnum()]
    return cleaned == cleaned[::-1]

Complexity: O(n) time and O(n) extra space for the cleaned copy and its reverse. This is already linear time; the follow-up is usually “do it without the extra memory”.

Approach 2: optimal

Key insight: a palindrome check only ever compares the i-th character from the left with the i-th from the right. Two pointers can skip ignored characters on the fly instead of building a cleaned copy.

Walkthrough on "Top spot":

left	right	Compare	Result
0 T	7 t	t = t	move in
1 o	6 o	o = o	move in
2 p	5 p	p = p	move in
3 space: skip to 4 s	4 s	pointers meet	True

def is_palindrome(s):
    left, right = 0, 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

Complexity: O(n) time, O(1) extra space.

Tests

import random

for f in (is_palindrome, is_palindrome_copy):
    assert f("Step on no pets!") is True
    assert f("Data, a tad!") is True
    assert f("Lazy data") is False
    assert f("  ,.") is True                 # only punctuation
    assert f("") is True                     # empty
    assert f("x") is True                    # single character
    assert f("0P") is False                  # digits are kept
    assert f("A1b1a") is True
    assert f("ab" * 100_000 + "a") is True   # long input

random.seed(19)
for _ in range(500):
    s = "".join(random.choice("aAbB1 ,!") for _ in range(random.randint(0, 8)))
    assert is_palindrome(s) == is_palindrome_copy(s)

Edge cases and pitfalls

• Keep the left < right guard inside the skipping loops, or a string of only punctuation runs a pointer off the end.
• Digits are kept, not skipped. isalpha instead of isalnum is a common slip.
• str.isalnum and str.lower accept Unicode letters too. If the interviewer restricts the problem to ASCII, say whether you rely on that.

Where this shows up in data engineering

Normalising strings before comparing them, by lowercasing and stripping punctuation, is a standard cleansing step before joining on names or deduplicating free-text fields. The palindrome itself is rare; the “normalise, then compare” habit is not.