Valid Palindrome (LeetCode 125)

The problem

You get a string s that can contain letters, digits, spaces and punctuation. Ignore everything that isn’t a letter or digit, treat upper and lower case as the same, and return True if what’s left reads the same forwards and backwards.

Input:  s = "No 'x' in Nixon"
Output: True

After dropping spaces and the apostrophes and lowering the case, you get "noxinnixon", which is the same reversed.

How to think about it

Start with brute force. Clean the string, build its reverse, and compare the two. That’s O(n) time and O(n) extra space, and honestly it’s an acceptable answer. But it doesn’t show the interviewer you know the pattern, and the follow-up is almost always “can you do it without building the reversed copy?”

The key insight: a palindrome is a mirror. Character 0 must equal the last character, character 1 must equal the second-to-last, and so on. So you never need the whole reversed string. You only need to compare pairs from the outside in, and you can stop at the first mismatch.

Two pointers do exactly that. Put i at the start and j at the end. If s[i] != s[j], it’s not a palindrome. Otherwise move both one step inward. When they meet or cross, every mirrored pair has matched.

Which pattern is this? Converging two pointers. The tell is “compare the two ends of a sequence and shrink towards the middle”.

Approach

1. Build a list of only the alphanumeric characters, lowercased.
2. Set i = 0 and j = len(s) - 1.
3. While i < j: if s[i] != s[j], return False; otherwise move i right and j left.
4. If the loop finishes, every pair matched, so return True.

To get O(1) extra space, skip the cleaning step and instead advance i (or retreat j) past non-alphanumeric characters inside the loop. The comparison logic is identical.

Solution

def is_palindrome(s):
    s = [c.lower() for c in s if c.isalnum()]   # keep letters/digits, ignore case
    i, j = 0, len(s) - 1
    while i < j:
        if s[i] != s[j]:                          # mirrored pair differs
            return False
        i += 1; j -= 1                            # both ends step inward
    return True
# is_palindrome("A man, a plan, a canal: Panama") -> True

Dry run

The cleaned list is n o x i n n i x o n (indices 0 to 9).

Next step makes i = 5, j = 4, so the loop stops and the function returns True.

Complexity

• Time: O(n). Cleaning is one pass, and the pointers together walk at most n/2 pairs.
• Space: O(n) for the cleaned list. The in-place skipping version uses O(1) extra space.

Edge cases and pitfalls

• Empty or symbol-only strings like "" or ".," clean down to nothing, and an empty string is a palindrome, so return True.
• Digits count. "0P" is not a palindrome: isalnum() keeps both 0 and p, and they differ.
• Case. Forgetting .lower() makes "Aa" fail.
• Loop condition. Use i < j, not i <= j. When they meet on the middle character, there’s nothing left to compare.
• In-place version off-by-one. When skipping symbols, also check i < j inside the skip loops, or a string of all punctuation runs a pointer off the end.

Related problems

• Two Sum II – Input Array Is Sorted (LeetCode 167): the same converging pointers, but deciding which end to move by a sum.
• Palindrome Linked List (LeetCode 234): the same mirror check when you can’t index from the back.
• Longest Palindromic Substring (LeetCode 5): pointers that expand outwards from a centre instead of converging.