LeetCode 125 · Two Pointers

Valid Palindrome, explained with a picture

Reading a sign from both ends.

EasyTwo Pointers
▶ Watch it step by step

The problem

A phrase is a palindrome if it reads the same forwards and backwards after you drop every character that is not a letter or digit and ignore upper/lower case. Decide whether the given phrase is one.

Input:  "No x in Nixon!"
Output: true   (cleaned: "noxinnixon")

Picture it

Picture two people reading a shop sign, one starting at the left end and one at the right. They skip spaces and punctuation and don’t care about capitals. Each compares their letter with the other’s and both take one step toward the middle. If any pair disagrees, it’s not a palindrome; if they meet in the middle, it is.

How to recognise it

  • You compare a sequence with its own reverse: the first item with the last, the second with the second-to-last.
  • That suggests two pointers, one at each end, moving towards each other.
  • Some characters must be skipped (anything that is not a letter or digit) and case ignored. A pointer can simply step past a character it should skip.
  • Strings can be up to 2 × 10^5 characters, so you want one pass and, ideally, no copies.

Start with brute force

Build the cleaned string (letters and digits only, lower-cased) and compare it with its reverse.

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

This is honestly fine for speed: O(n) time. Its cost is memory. It builds a cleaned copy and a reversed copy, each up to 2 × 10^5 characters, so O(n) extra space, and it always reads the whole string even when the first and last characters already differ.

From brute force to the idea

  1. Find the waste. The reversed copy is only used to compare position i from the front with position i from the back. You can read both directly from the original string.
  2. Two pointers. Put l at the start and r at the end. While l < r, they point at a pair that must match.
  3. Skip, one step at a time. If s[l] is not a letter or digit, move l right and try again. Do the same for r, moving left. Each loop round does exactly one thing, which keeps the logic simple.
  4. Compare ignoring case. When both point at letters or digits, compare s[l].lower() with s[r].lower(). A mismatch means it is not a palindrome, so return at once.
  5. Move inwards. On a match, step both pointers. When they meet or cross, every pair has matched.

This is the key idea: two pointers from both ends, skipping what does not count, with no cleaned copy.

The key idea

Two pointers from both ends, skipping non-letters, compare as you go: O(n) time, no extra copy of the string.

Python solution

def is_palindrome(s):
    l, r = 0, len(s) - 1
    while l < r:
        if not s[l].isalnum():
            l += 1
        elif not s[r].isalnum():
            r -= 1
        elif s[l].lower() != s[r].lower():
            return False
        else:
            l, r = l + 1, r - 1
    return True

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.

Complexity

ApproachTimeSpace
Clean and reverse (brute force)O(n): one pass to clean, one to reverse, one to compareO(n): the cleaned and reversed copies
Two pointers (shown code)O(n): each round moves at least one pointer inwardsO(1): two indices

Edge cases

  • Empty string or only spaces and punctuation (" ", ".,"): returns True. The pointers skip everything and meet, and an empty cleaned string counts as a palindrome.
  • One character: returns True; the loop never runs.
  • Digits count ("0P"): returns False. 0 is kept, and 0 is not p.
  • Underscore is skipped ("ab_a"): returns True. _ is not a letter or digit in Python.
  • Mixed case ("Aa"): returns True thanks to .lower().
  • Non-ASCII: Python's isalnum also accepts characters such as é and ². LeetCode's input is printable ASCII, so this never matters there, but it does for general text.

Common mistakes

  • Forgetting .lower(), so "Aba" returns False.
  • Building the cleaned string anyway and then running two pointers on it, which keeps the O(n) memory the pointers were meant to save.
  • Skipping with an inner while loop that does not check l < r, so on a string of only punctuation the pointer runs off the end and raises IndexError.
  • Using isalpha instead of isalnum, which drops digits that should be compared.
Your turn: one deletion allowed

Given a lowercase string, return True if it can become a palindrome after deleting at most one character. "abca" returns True (delete c or b), and "abc" returns False. Describe your approach, then write it if you like.

Compare with our answer

Run the same two pointers. At the first mismatch, one of the two characters must be the one you delete. Try both: check whether s[l+1..r] or s[l..r-1] is a palindrome. You only get one deletion, so those checks use plain matching with no further skips.

def valid_palindrome_one_delete(s):
    def is_pal(l, r):
        while l < r:
            if s[l] != s[r]:
                return False
            l, r = l + 1, r - 1
        return True
    l, r = 0, len(s) - 1
    while l < r:
        if s[l] != s[r]:
            return is_pal(l + 1, r) or is_pal(l, r - 1)
        l, r = l + 1, r - 1
    return True

"deeee" returns True by deleting the d. Time O(n), because each of the two final checks is one pass. Space O(1).

A strong answer mentions: branching only at the first mismatch, trying both deletions, and why that keeps it O(n) rather than trying every deletion in O(n²).

Check what stuck

1. You must reverse only the letters of a string, leaving digits and punctuation exactly where they are. Which approach fits best?

2. Why does the shown code use O(1) extra space?

3. A learner writes elif s[l] != s[r]: without the .lower() calls. Which input now gets the wrong answer?

Score 60% or more and the lesson is marked complete.