Valid Palindrome: Two Pointers From Both Ends

Valid palindrome is usually the first string question in a screen, and it looks too easy to get wrong. Then the details arrive: ignore punctuation, ignore case, do it without building a cleaned copy, and, as a follow-up, allow one character to be deleted. Each detail is a small trap. The two-pointer version handles all of them in one pass with two integers of state.

The problem it solves

Given a string, decide whether it reads the same forwards and backwards once you keep only letters and digits and ignore letter case. "A man, a plan, a canal: Panama" is a palindrome; "race a car" is not, because once the spaces are gone, raceacar has an e where its mirror position holds an a.

The one-line answer is to clean the string and compare it with its reverse:

• Clean, then reverse. Filter to alphanumerics, lower-case, compare with [::-1]. Correct, O(n) time, but it allocates two new strings of up to n characters.
• Two pointers. Read from both ends at once, skip what does not count, compare what does. Same O(n) time, O(1) extra memory, and it stops at the first mismatch instead of after building everything.

An interviewer who accepts the first will almost always ask for the second.

The intuition

A palindrome is a string whose first character equals its last, whose second equals its second-to-last, and so on inward. So check exactly those pairs. Put left at index 0 and right at the last index, and repeat:

• If left is on something that is not a letter or digit, move left only.
• Otherwise, if right is on junk, move right only.
• Otherwise compare the two characters, lower-cased. A mismatch is a definite no.
• A match settles two characters at once, so both pointers step inward.

The loop ends when the pointers meet or cross. A lone middle character, in an odd-length palindrome, has nothing to disagree with, so it is never compared. Meeting in the middle without a mismatch is a definite yes.

The skipping is the part people get wrong. You skip one pointer at a time, and you re-check the loop condition after every skip, because a string made entirely of punctuation must not walk a pointer off the end.

Watch it run

The animation checks "RaceCar!" with two pointers and no reversed copy. It starts with the idea itself: a palindrome reads the same both ways, so read it from both ends at once. The right pointer lands on "!", which is not alphanumeric, so it skips it and moves that pointer only. Now R faces r; lower-cased they are the same letter, so both pointers step inward. a and a match, and each comparison settles two characters at once. Then c against C: the third pair, and still nothing has been allocated. The pointers meet on the middle e, a lone middle character with nothing to disagree with. Verdict: palindrome, in three comparisons and O(1) extra memory.

The code

The lesson's function, one branch per case:

def is_palindrome(s):
    left, right = 0, len(s) - 1
    while left < right:
        if not s[left].isalnum():          # skip junk from the left
            left += 1
        elif not s[right].isalnum():       # ...and from the right
            right -= 1
        elif s[left].lower() != s[right].lower():
            return False                   # one mismatch is enough
        else:
            left, right = left + 1, right - 1
    return True

print(is_palindrome("RaceCar!"))                         # True
print(is_palindrome("A man, a plan, a canal: Panama"))   # True
print(is_palindrome("race a car"))                       # False
print(is_palindrome(",.!"))                              # True   nothing left to compare

The comparisons it actually makes on the animation's input, as (left, right, pair):

def trace(s):
    left, right, log = 0, len(s) - 1, []
    while left < right:
        if not s[left].isalnum():
            left += 1
        elif not s[right].isalnum():
            right -= 1
        else:
            log.append((left, right, s[left] + s[right]))
            if s[left].lower() != s[right].lower():
                break
            left, right = left + 1, right - 1
    return log

for row in trace("RaceCar!"):
    print(row)
# (0, 6, 'Rr')
# (1, 5, 'aa')
# (2, 4, 'cC')

The standard follow-up allows deleting at most one character. Run the same scan; at the first mismatch, the only possible fixes are dropping the left character or dropping the right one, so check both remaining windows with the plain two-pointer test. Anything before the mismatch already matched and never needs checking again:

def is_pal_range(s, lo, hi):
    while lo < hi:
        if s[lo] != s[hi]:
            return False
        lo, hi = lo + 1, hi - 1
    return True

def valid_with_one_delete(s):
    lo, hi = 0, len(s) - 1
    while lo < hi:
        if s[lo] != s[hi]:                 # first mismatch: two ways out
            return is_pal_range(s, lo + 1, hi) or is_pal_range(s, lo, hi - 1)
        lo, hi = lo + 1, hi - 1
    return True

print(valid_with_one_delete("abca"))       # True    drop 'b' or 'c'
print(valid_with_one_delete("abc"))        # False
print(valid_with_one_delete("deeee"))      # True    drop the 'd'

Both functions against brute force on 20,000 random strings, where the brute force cleans and reverses, and for the deletion version tries every single deletion:

import random

def brute_palindrome(s):
    kept = [c.lower() for c in s if c.isalnum()]
    return kept == kept[::-1]

def brute_one_delete(s):
    options = [s] + [s[:i] + s[i + 1:] for i in range(len(s))]
    return any(t == t[::-1] for t in options)

random.seed(20)
ok = True
for _ in range(20000):
    s = "".join(random.choice("abAB1 ,!") for _ in range(random.randint(0, 9)))
    ok &= is_palindrome(s) == brute_palindrome(s)
    t = "".join(random.choice("abc") for _ in range(random.randint(0, 9)))
    ok &= valid_with_one_delete(t) == brute_one_delete(t)
print(ok)                                  # True

The complexity

• Time: O(n). Every step moves at least one pointer inward, so there are at most n steps in total, skips included.
• Space: O(1). Two indices; no cleaned copy, no reversed copy.
• Early exit: the scan stops at the first mismatch, while clean-and-reverse always pays for the full copy first.
• One-deletion version: still O(n). The main scan plus at most two range checks, each over part of the string, and never more than two.

Where it goes wrong

• Skipping with an inner while that ignores the bounds. while not s[left].isalnum(): left += 1 runs off the end of ",.!". Either keep the left < right check inside the skip, or skip one step per loop iteration as above.
• Forgetting digits. The usual definition keeps letters and digits, so isalpha is wrong; "0P" is not a palindrome.
• Comparing before lower-casing. R and r must count as the same letter.
• Trying to fix every mismatch in the deletion version. You get one deletion. After the first mismatch the two windows must be palindromes outright, with no further skipping.
• Checking only one window. In "deeee" dropping the right character fails and dropping the left one works; test both.

When it shows up in interviews

It is a common warm-up in phone screens and a standard first question on the two-pointer pattern, listed alongside it on the patterns cheat sheet. Interviewers use it to watch how you handle the skip conditions and the empty or all-punctuation string, then ask for the one-deletion variant. The same inward expansion, run from the centre outwards instead, is how you find the longest palindromic substring.

How to say it in an interview

"A palindrome matches its mirror pair by pair, so I compare from both ends instead of building a cleaned, reversed copy. Left and right pointers start at the ends. If either is on a non-alphanumeric character I move just that pointer; otherwise I compare the two characters lower-cased. A mismatch returns false, and a match moves both inward, settling two characters at once. When they meet, it is a palindrome. That is linear time and constant space. If one deletion is allowed, I run the same scan and, at the first mismatch, check whether either the window without the left character or the one without the right character is a palindrome."