Palindrome Validation

One mismatched pair tells you where to look

Can "abca" become a palindrome if you delete at most one character? The obvious plan is to try every deletion ("bca", "aca", "aba", "abc") and test each one. With four letters that's fine. LeetCode 680: Valid Palindrome II allows 100,000 letters. That means 100,000 candidate strings, each about 100,000 characters to build and check: roughly 10¹⁰ character steps. On a laptop, a Python version of that plan took 4.9 seconds on one 100,000-letter input where no deletion works. The version you'll build in this lesson makes at most n comparisons, a few milliseconds for 100,000 letters (6 microseconds on that same input).

The speed-up comes from how you check an ordinary palindrome. Compare the outermost pair of characters, then the next pair in, and stop at the first pair that disagrees. In "abca" that pair is b and c, at indices 1 and 2. That one pair tells you where the problem is: one of those two characters has to go. So there are two deletions worth trying, not n.

That is the whole lesson: a palindrome check compares mirror pairs from the outside in. Most problems here change one of three things: which pairs count, what to do at the first pair that disagrees, or how you reach the back half.

This lesson builds on Two Pointer Techniques: two indices that start at opposite ends and walk toward each other. It also builds on Foundation: Arrays & Strings. Its reverse(nums, lo, hi) is the same loop as ours, with a swap where we will put a comparison. From that lesson you also need two facts: Python strings are immutable, and a slice builds a new list. A reversed string slice such as s[::-1] is likewise a full new copy. Two neighboring problems are not checks. Rearranging letters into a palindrome is a counting problem, and Foundation's count-parity trick solves it. Finding the longest palindrome inside a string is a search, covered in String Algorithms.

Move 1: The mirror test

Smell: "the same forwards and backwards."

In a string of length n, index i and index n − 1 − i are a mirror pair. The string is a palindrome exactly when every mirror pair holds equal characters. You only need the pairs with i < n // 2. The rest are the same pairs seen from the other side, and in an odd-length string the middle character is its own mirror.

Predict first: how many character comparisons does it take to confirm that "racecar" is a palindrome? Which character never gets compared with anything?

The one-liner, and what it wastes

def is_palindrome_copy(s):
    return s == s[::-1]

It's correct, it's O(n) time, and in CPython it's hard to beat. On a clean 1,000,000-character palindrome it took about 0.5 ms, against about 16 ms for the loop below, because the reversal and the comparison both run in C. Keep it for quick scripts.

Look at what it does, though. It builds a full reversed copy (O(n) extra space) before comparing anything, even when the first pair already disagrees. Then, on a palindrome, it compares every mirror pair twice, once from each side, plus the middle character with itself. And it can't be bent. You can't tell it to skip punctuation or allow one mistake, and you can't point it at part of the string without slicing another copy. Every problem after this one needs one of those things.

Two pointers, one mirror

def is_palindrome(seq) -> bool:
    left, right = 0, len(seq) - 1
    while left < right:
        if seq[left] != seq[right]:
            return False          # one bad pair is proof
        left += 1
        right -= 1
    return True                   # every pair matched

It works on anything you can index: strings, lists, tuples. Here is what it compares on three inputs:

Why it works. Here is the loop invariant: before each test of left < right, every mirror pair outside the window [left, right] has matched. So the whole sequence is a palindrome exactly when the window is. Each step removes one matched pair from the window. When left >= right, the window holds one element or none, and both of those read the same backwards. A single mismatched pair proves the answer is no, so returning immediately is safe.

Edge cases. For an empty sequence right is −1, the loop never runs, and the answer is True. For one element, left == right from the start, and the answer is also True. The condition must be left < right. With left <= right the loop also compares the middle element with itself, which is harmless but wasted. With left != right, an even-length palindrome breaks: on "abba" the pointers step past each other at (2, 1) and keep going until seq[4] raises IndexError.

Cost. Let n be the length. The loop makes at most n // 2 comparisons, so it takes O(n) time and O(1) extra space: two integers.

Why not recursion?

The recursive definition is pretty: a string is a palindrome if its ends match and its middle is a palindrome.

def is_palindrome_rec(s):
    if len(s) <= 1:
        return True
    return s[0] == s[-1] and is_palindrome_rec(s[1:-1])

Count what it costs. Each call slices the middle, copying n − 2 characters, then n − 4, and so on. That totals about n²/4 characters, so the time is O(n²). It also nests about n/2 calls deep. CPython's default recursion limit is 1,000, and on this machine the function raised RecursionError at 1,998 characters. Under that default it fails far below the sizes the two main LeetCode string problems here allow (10⁵ and 2·10⁵ characters). Raising the limit with sys.setrecursionlimit swaps the crash for n/2 stack frames, and the slicing still costs O(n²). Passing indices instead of slices removes the copying but not the depth, because Python never turns tail calls into loops. The while loop above is this same recursion with the call stack removed.

Your turn: check a slice without slicing

Write is_pal_range(seq, lo, hi). It returns whether seq[lo..hi] (both ends inclusive) is a palindrome, in O(1) extra space. Predict is_pal_range("xabay", 1, 3), is_pal_range("xabay", 0, 4) and is_pal_range("xabay", 3, 2).

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

Move 2: Skip what doesn't count

Smell: the statement tells you to ignore some characters, or to ignore case.

LeetCode 125: Valid Palindrome. A phrase counts as a palindrome if it reads the same both ways after you lowercase every letter and remove every character that isn't a letter or a digit. The input has 1 to 2·10⁵ characters, all printable ASCII.

Predict first: which of these should return True?

1. "A man, a plan, a canal: Panama"
2. "race a car"
3. " "
4. "0P"
5. "ab_a"

The slow version: clean, then compare

def is_valid_palindrome_copy(s: str) -> bool:
    cleaned = "".join(ch.lower() for ch in s if ch.isalnum())
    return cleaned == cleaned[::-1]

This is correct and LeetCode accepts it. It takes O(n) time and O(n) extra space: cleaned, its reversed copy, and, in CPython, the temporary list that join builds from the generator. As a first answer in an interview it's fine. Say so, then offer the follow-up interviewers usually ask for: the same check with no copy.

Look at what the copy holds. It's a second copy of characters that are already sitting in s. The comparisons you need are cleaned[k] against cleaned[m − 1 − k], where m is the cleaned length. Both of those characters are somewhere in s, so all you need is a way to reach them.

Skip as you go

Let each pointer walk past whatever the cleaner would have deleted, and lowercase at the moment you compare:

def is_valid_palindrome(s: str) -> bool:
    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

Trace "Madam, I'm Adam". It has 15 characters:

 M  a  d  a  m  ,     I  '  m     A  d  a  m
 0  1  2  3  4  5  6  7  8  9 10 11 12 13 14

After step 6, left is 8 and right is 6, so the loop ends and the function returns True. In the last step the skip loops pushed both pointers onto the middle character, which gets compared with itself. That's harmless.

Why it works. Skipping as it goes, the left pointer visits the letters and digits in the order they appear in cleaned. The right pointer visits the same characters in reverse order. So the k-th comparison is cleaned[k] against cleaned[m − 1 − k], exactly the pairs Move 1 would compare on the copy. The invariant from Move 1 still holds, restated for noise: every letter or digit outside [left, right] has been matched with its mirror.

Cost. Here n is len(s), counting every character, noise included. Both pointers only move inward, so together they take at most n steps: O(n) time. Each s[i] is an O(1) read, because CPython stores every string with one fixed width per character. The extra space is two integers. s[left].lower() creates a one-character string that is thrown away at once, so the extra space is O(1). On a 1,000,000-character noisy palindrome, both versions took about 40–45 ms. The copy version peaked at about 31 MB of extra memory; the two-pointer version peaked under 100 bytes. When the very first pair mismatched, the two-pointer version returned in under a microsecond, while the copy version still spent 40 ms building its copy. The win is memory and early exit, not raw speed on a full palindrome.

Edge cases worth a test

• Nothing but noise. On ".," the left pointer skips to index 1, the right loop stops immediately because left < right is already false, and , is compared with itself. The function returns True, which is right: nothing is left after cleaning.
• right = len(s) isn't a subtle bug in Python. Every non-empty input raises IndexError on the first read of s[len(s)], and "" survives only because the loop never runs.
• "Helpful" early exits. if len(s) <= 1: return True is redundant but harmless. if not s.strip(): return False is a real bug, because " " must return True.
• Beyond ASCII, isalnum() follows Unicode rules: '½'.isalnum() and '²'.isalnum() are both True. LeetCode 125's input is printable ASCII, where isalnum() means exactly A–Z, a–z and 0–9. For real text, decide the policy on purpose.

Your turn: break it on purpose

Each edit below turns is_valid_palindrome into a bug that returns the wrong Boolean on some input without crashing. Find an input for each one.

1. isalnum() replaced by isalpha() in both skip loops.
2. The left < right and removed from the left skip loop only.
3. Both skip loops replaced by one check at the top of the outer loop: if not s[left].isalnum() or not s[right].isalnum(): left += 1; right -= 1; continue.

Bonus: what does edit 2 do on ".,"?

Move 3: One deletion allowed

Smell: the input is almost a palindrome, and the problem gives you a budget of one mistake.

LeetCode 680: Valid Palindrome II. Return True if s can be a palindrome after deleting at most one character. There are 1 to 10⁵ lowercase letters.

Predict first: the first mismatched pair in "abca" is at indices 1 and 2. Which deletions are worth trying? Why is deleting index 0 not worth trying?

The slow version tries every deletion

def valid_palindrome_ii_slow(s: str) -> bool:
    if s == s[::-1]:
        return True
    for i in range(len(s)):
        t = s[:i] + s[i + 1:]          # a new string of n - 1 characters
        if t == t[::-1]:
            return True
    return False

This is O(n) work per candidate for n candidates: O(n²). It's the 4.9-second version from the start of the lesson. What it repeats is the entire palindrome check, once per candidate, even though one pass over s already shows where the trouble is.

Let the first mismatch choose

def valid_palindrome_ii(s: str) -> bool:
    left, right = 0, len(s) - 1
    while left < right:
        if s[left] != s[right]:
            return (is_pal_range(s, left + 1, right)      # delete s[left]
                    or is_pal_range(s, left, right - 1))  # delete s[right]
        left += 1
        right -= 1
    return True                                           # no deletion needed

is_pal_range is your function from Move 1. Trace "abcdcbea":

It returns True: deleting the e leaves abcdcba. On "abca" the first candidate, is_pal_range(s, 2, 2), is already True, so or never runs the second one.

Cost. The main loop stops at the first mismatch. After that come at most two scans of the middle, and each makes at most half as many comparisons as the middle has characters. In total the function never makes more than n character comparisons, where n is len(s): O(n) time, O(1) extra space. If you check the two candidates with slices instead (t = s[left + 1:right + 1]; t == t[::-1]), it's still O(n) time but the copies cost O(n) space.

Why two candidates are enough

Two facts carry the proof.

1. Matching ends are free. If s[l] == s[r], then s[l..r] can be fixed with at most one deletion exactly when s[l+1..r-1] can. So the loop can walk past matched pairs and never reconsider them.
2. At a mismatch, one end must go. Say s[l] != s[r] in the stretch s[l..r] that fact 1 leaves you with. If you delete neither end, then whatever you delete in between, the result still starts with s[l] and ends with s[r], so it isn't a palindrome. The single deletion must remove s[l] or s[r]. After that no deletions are left, so what remains, s[l+1..r] or s[l..r-1], must already be a palindrome.

Fact 1 is what lets the first mismatch speak for the whole string. Fact 2 turns that mismatch into exactly two range checks.

Shortcuts that look right

⚠️ Peeking one character ahead. A popular shortcut decides which side to drop by looking at the next character: "if s[left + 1] == s[right], drop the left one, otherwise drop the right one". It fails on "abbab". At the first mismatch (a vs b at 0 and 4) the peek sees s[1] == s[4], drops the left a, and gets stuck on bbab. Dropping the last b gives abba. When both sides look fine after one character, only a full check can tell them apart.

⚠️ Other one-line slips, each checked against the brute force:

• is_pal_range(s, left + 1, right - 1) deletes both ends. That's two deletions, and it returns True for "abc".
• and instead of or demands that both deletions work. It returns False for "aab".
• Calling valid_palindrome_ii itself on the smaller ranges lets every level spend another deletion. It returns True for "abc".

When one deletion becomes k

LeetCode 1216: Valid Palindrome III (a premium problem) allows up to k deletions, with n ≤ 1000. Branching at every mismatch now means up to about 2ᵏ paths, each scanning up to n characters. The standard tool is dynamic programming. The fewest deletions that turn s into a palindrome equals len(s) minus the length of its longest palindromic subsequence, which an O(n²) table computes. For example, "abcdeca" needs 2 deletions (drop b and e). That length also equals the longest common subsequence of s and s[::-1]. See Dynamic Programming Mastery and 2D DP & Grid Problems.

Your turn: noise and one deletion

Combine Moves 2 and 3. Ignore case and every character that isn't a letter or digit, and allow at most one deletion. Predict the results for "race a car", "0P" and "ab, cd".

def first_mismatch(s, lo, hi):
    """First (lo, hi) pair of letters/digits that disagree in s[lo..hi], or None."""
    while lo < hi:
        while lo < hi and not s[lo].isalnum():
            lo += 1
        while lo < hi and not s[hi].isalnum():
            hi -= 1
        if s[lo].lower() != s[hi].lower():
            return lo, hi
        lo += 1
        hi -= 1
    return None

def valid_palindrome_one_deletion(s: str) -> bool:
    bad = first_mismatch(s, 0, len(s) - 1)
    if bad is None:
        return True
    lo, hi = bad
    return first_mismatch(s, lo + 1, hi) is None or first_mismatch(s, lo, hi - 1) is None

Move 4: Plot twist, no right pointer

Smell: the data only hands you elements from one end. An integer gives up its digits from the low end (x % 10). A singly linked list only walks forward.

LeetCode 9: Palindrome Number. Return whether the integer x reads the same backwards (121 → True, -121 → False, 10 → False), where −2³¹ ≤ x ≤ 2³¹ − 1. The follow-up asks you to solve it without converting x to a string.

Predict first: split 1221 and 12321 into a front half and a back half. Read each back half backwards. What do you notice?

str(x) == str(x)[::-1] works, but it's what the follow-up forbids, and it builds strings of d characters, where d is the digit count. Reversing the whole number is fine in Python, whose integers never overflow. In Java or C++ with a 32-bit int, reversing 2,147,483,647 gives 7,463,847,412, which doesn't fit. That is why the standard solution reverses only half:

def is_palindrome_number(x: int) -> bool:
    if x < 0 or (x % 10 == 0 and x != 0):
        return False
    back = 0
    while x > back:
        back = back * 10 + x % 10     # move x's last digit onto back
        x //= 10
    return x == back or x == back // 10   # even digit count, or odd (drop the middle)

Why it works. The invariant: back is the digits removed from x, in reverse order. The loop stops once back is at least as large as what's left of x, and by then back has at least as many digits. With an even digit count the two halves must be equal. With an odd count the middle digit ended up as back's last digit, and back // 10 drops it.

The guard earns its place. A negative number can't be a palindrome, because the - has no mirror. A number that ends in 0 can't be one either, because it can't start with 0. The only exception is 0 itself. Leave out the trailing-zero check and 10 goes to (1, 0) → (0, 1), then 0 == 1 // 10 is True, which is wrong. So are 100 and 110.

Cost. For d digits the loop runs about d/2 times: O(d) = O(log |x|) time and O(1) space. For any 32-bit input, back never has more than 6 digits, so it can't overflow.

Your turn: base 2

Is the binary representation of a non-negative integer n a palindrome? Write it without bin() or strings, then predict n = 9, 6 and 0.

def is_binary_palindrome(n: int) -> bool:
    if n < 0 or (n % 2 == 0 and n != 0):
        return False
    back = 0
    while n > back:
        back = back * 2 + n % 2
        n //= 2
    return n == back or n == back // 2

The same idea works on a singly linked list: you can't walk it backwards, but you can reverse its back half in place. That's your third challenge in the final round.

Final round: no label on the problem

Real problems don't say which move they need. Read the statement, find the smell, pick the move.

Challenge 1: one replacement

Can s become a palindrome by changing at most one character, to any other character? Predict "abca", "abc" and "abcd". Why doesn't this need Move 3's branching?

def one_replacement(s: str) -> bool:
    n = len(s)
    mismatches = sum(1 for i in range(n // 2) if s[i] != s[n - 1 - i])
    return mismatches <= 1

Challenge 2: any order you like

Can the letters of s be rearranged into a palindrome? Predict "carrace" and "code".

Challenge 3: a list you can't walk backwards

LeetCode 234: Palindrome Linked List. Given the head of a singly linked list, return whether its values form a palindrome. The list has up to 10⁵ nodes. The follow-up asks for O(n) time and O(1) extra space.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def is_palindrome_list_copy(head) -> bool:      # O(n) extra space
    values = []
    while head:
        values.append(head.val)
        head = head.next
    return is_palindrome(values)                # Move 1

def reverse_list(head):
    prev = None
    while head:
        nxt = head.next
        head.next = prev
        prev, head = head, nxt
    return prev

def is_palindrome_list(head) -> bool:           # O(1) extra space
    slow = fast = head
    while fast and fast.next:                   # slow ends at the middle
        slow = slow.next
        fast = fast.next.next
    back = reverse_list(slow)                   # back half, now walking backwards
    a, b, ok = head, back, True
    while b:                                    # the back half is never longer
        if a.val != b.val:
            ok = False
            break
        a, b = a.next, b.next
    reverse_list(back)                          # put the caller's list back
    return ok

Cheat sheet

Before moving on, close this page and solve Valid Palindrome II from a blank editor. Then explain out loud: why the matched outer pairs never need a second look, why exactly two candidates remain at the first mismatch, and which input breaks the peek-ahead shortcut. If you can also say how the answer changes when "delete" becomes "replace", you own this lesson.

Next: Container With Most Water uses the same converging pointers to optimize rather than check, and it needs a real proof for which pointer to move. String Algorithms turns this lesson's invariant around: if s[l..r] is a palindrome and s[l−1] == s[r+1], so is s[l−1..r+1]. Growing outward from each center is how you find palindromic substrings. Sliding Window Patterns moves both pointers in the same direction, which is a different family.