Valid Palindrome

A palindrome check is the symmetric form of converging pointers: instead of comparing a sum to a target, you compare the character at each end and walk inward. The problem looks easy, and it is — which is why interviewers grade it on the details. Can you skip characters safely, handle case, and avoid building copies of the string?

The problem

Given a string, decide whether it reads the same forwards and backwards when you look only at letters and digits and ignore upper and lower case.

• "Race, car!" → True. Keeping letters and digits and lower-casing gives "racecar", which is the same reversed.
• "Madam, I'm Eve" → False. The cleaned text "madamimeve" reversed is "evemimadam".

Constraints: 0 ≤ len(text) ≤ 2 × 10⁵; printable ASCII characters. Aim for O(1) extra space.

Clarifying questions

• What counts as a character to compare? Letters and digits only; spaces and punctuation are skipped.
• Is "A" equal to "a"? Yes, case is ignored.
• Empty string, or only punctuation? Both count as palindromes — there is nothing that fails to match.
• Unicode letters? Assume ASCII; say that str.isalnum would also accept other scripts.

Approach 1: the simple way

Build the cleaned, lower-cased text and compare it with its reverse.

1def is_palindrome_simple(text: str) -> bool:2    """Keep letters and digits, lower-case them, compare with the reverse."""3    cleaned = [ch.lower() for ch in text if ch.isalnum()]4    return cleaned == cleaned[::-1]

Time O(n), space O(n). This is not too slow — it is linear, and it is a perfectly good first answer to say out loud. The weakness is memory: it builds a cleaned copy and then a reversed copy, two extra lists of up to 2 × 10⁵ characters. The interviewer's follow-up is always "can you do it without the copies?"

The key insight

A palindrome is a set of mirror pairs: position 0 with the last position, 1 with the second-to-last, and so on. You never need the whole cleaned string — only the next valid character from each end. So keep one pointer at each end, let each one step over characters that do not count, and compare what they land on. The first mismatch proves the answer is False; if the pointers meet without a mismatch, it is True.

The skipping is the only new part. Each pointer must skip non-alphanumeric characters on its own side, and it must never cross the other pointer while doing so.

Approach 2: converging pointers with skipping

1def is_palindrome(text: str) -> bool:2    """True if text reads the same both ways, looking only at letters and digits."""3    left, right = 0, len(text) - 14    while left < right:5        while left < right and not text[left].isalnum():6            left += 1                    # skip punctuation on the left7        while left < right and not text[right].isalnum():8            right -= 1                   # skip punctuation on the right9        if text[left].lower() != text[right].lower():10            return False11        left += 112        right -= 113    return True

1. Start at both ends.
2. Move left right past anything that is not a letter or digit; move right left the same way. Both inner loops keep the left < right guard.
3. Compare the two characters, lower-cased. A mismatch ends the search.
4. Step both pointers inward — both, because this matched pair is finished — and repeat.

Dry run on "Race, car!" (positions: R0 a1 c2 e3 ,4 space5 c6 a7 r8 !9):

After round 4, left = 4 and right = 2, so the loop ends and the function returns True. Look at round 4: the right pointer skipped the space and the comma and then stopped because it reached left. The middle e is compared with itself, which is harmless.

Now a failing input. On "Madam, I'm Eve" the very first round compares M (position 0) with e (position 13), finds a mismatch, and returns False after one comparison. Approach 1 would first have built two full copies of the cleaned text. Early exit is a small, real advantage of the pointer version: most non-palindromes fail near the ends.

Why both pointers move after a match. Once text[left] and text[right] match, that mirror pair is finished; neither character is needed again. Moving only one pointer would compare a finished character with a new one, which is a different question and gives wrong answers on inputs like "abba".

Complexity. The nested loops look quadratic, but they are not. Every step of every loop moves left right or right left, and the two pointers together move only about n times before they cross. On the 10-character "Race, car!", the pointers made 11 moves in total across all three loops. O(n) time, O(1) space.

Edge cases

• Empty string. right = -1, the loop never runs → True.
• Only punctuation, such as ",.;". The inner loop walks left up to right and stops there; one character is compared with itself → True. Without the left < right guard in the inner loops, left would run past the end and raise IndexError.
• Mixed letters and digits, such as "0P". '0' vs 'p' → False. Digits count as real characters; code that only checks isalpha gets this wrong.
• One valid character surrounded by punctuation, such as "a.". → True.
• Characters outside ASCII. Python's isalnum also says yes to "é", to the superscript "²" and to digits from other scripts. For the ASCII input promised here that never matters, but if the interviewer widens the input, say so — and mention that casefold() handles cases lower() does not, such as German "ß" matching "ss". A strict ASCII check is ch.isascii() and ch.isalnum().

We tested the pointer version against Approach 1 on 600 random strings built from letters in both cases, a digit, spaces and punctuation — half of them forced to be palindromes, so both answers were well covered. They agreed on every one.

Follow-ups

• "You may delete at most one character." That is the next lesson, Valid Palindrome II: on the first mismatch, try skipping the left character or the right one.
• "Check a number without converting it to a string." Reverse half the digits with % 10 and // 10 and compare halves; negative numbers are never palindromes.
• "The text is a stream you can read only once." Two pointers need random access. Compare a rolling hash of the text read forwards with one built backwards; state that it is probabilistic.