Valid Palindrome II: One Deletion Palindrome Check

LeetCode 680, Valid Palindrome II, builds directly on the classic valid palindrome problem. This time you are allowed to delete at most one character. The question: can you make the string a palindrome by removing zero or one characters?

This small change turns a simple two pointer scan into something a bit more interesting. When the two pointers hit a mismatch, you have a decision to make. Do you skip the left character, or skip the right one? The answer is: try both.

The problem

Given a string s, return True if the string can be a palindrome after deleting at most one character from it.

Examples:

• "aba" is already a palindrome. Return True.
• "abca" can become "aba" (delete 'c') or "aca" (delete 'b'). Return True.
• "abc" cannot become a palindrome with one deletion. Return False.

The approach

Start with the same two pointer setup from Valid Palindrome. Place left at the start and right at the end. Move them inward, comparing characters at each step.

If every pair matches, the string is already a palindrome. No deletion needed.

If you hit a mismatch, you have one deletion to spend. There are exactly two options:

1. Skip the left character. Check if s[left+1..right] is a palindrome.
2. Skip the right character. Check if s[left..right-1] is a palindrome.

If either substring is a palindrome, the answer is True. If neither is, even one deletion cannot save it.

The solution

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

    left, right = 0, len(s) - 1

    while left < right:
        if s[left] != s[right]:
            return is_palindrome(left + 1, right) or is_palindrome(left, right - 1)
        left += 1
        right -= 1

    return True

The helper is_palindrome(lo, hi) is a standard two pointer palindrome check on the substring s[lo..hi]. The outer loop runs the normal convergence. The moment it finds a mismatch, it branches into two checks and returns the result immediately.

Visual walkthrough

Let's trace the algorithm on the string "abca". L (orange) is the left pointer, R (green) is the right pointer.

At step 2, the pointers land on 'b' and 'c', which do not match. The algorithm tries both skip paths. Skipping the left character leaves "ca" to check (just index 2 to 2 after the outer pair is confirmed). Skipping the right character leaves "b" to check (index 1 to 1). Both single-character substrings are trivially palindromes, so the answer is True.

Why not try every deletion?

A brute force approach would try deleting each character one at a time and checking if the remaining string is a palindrome. That is O(n^2) total work. The two pointer approach avoids this because it narrows the problem down to exactly one critical point: the first mismatch.

Everything before the mismatch already matches from both ends. Everything after the mismatch has not been checked yet, but it will be checked by the helper function. The mismatch is the only place where a deletion could help.

Complexity analysis

Time: O(n). The outer loop and the helper each scan at most n characters total. Even though the helper might scan up to n-2 characters, it only runs once (at the first mismatch). The combined work is still linear.

Space: O(1). Only pointer variables. No extra strings or arrays.

The building blocks

Valid Palindrome II is built from two pieces that show up across many problems.

Opposite-end convergence

Two pointers start at the ends and move inward. This is the same skeleton as the basic palindrome check, Two Sum II on a sorted array, and Container With Most Water. The core idea: shrink the search space from both sides by one element per step.

Greedy branching at first conflict

When the pointers disagree, you make a greedy choice rather than backtracking. Instead of exploring all possibilities, you try at most two options at the exact point of conflict. This same "try both and take the best" pattern appears in problems like removing obstacles in a grid or checking if a sequence can be made valid with one fix.

The combination of these two blocks is what makes the solution elegant. The outer convergence handles the happy path. The branch handles the one exception you are allowed.

Edge cases

Already a palindrome. The pointers never mismatch. The outer loop finishes and returns True. No deletion needed.

Single character or empty string. A single character is always a palindrome. An empty string is a palindrome by definition. Both return True immediately since left is not less than right.

Mismatch at the very first pair. For "ba", left=0 and right=1 mismatch immediately. The helper checks s[1..1] (just "a") and s[0..0] (just "b"). Both are single characters, so both are palindromes. Return True.

Two mismatches needed. For "abc", the first pair 'a' and 'c' mismatch. Skipping left gives "bc" (not a palindrome). Skipping right gives "ab" (not a palindrome). Return False.

Long string with mismatch near the middle. The outer loop does half the work, then the helper does the other half. Total work is still O(n).

Reading about it is not enough

Valid Palindrome II is rated easy, and the solution is short. But writing it from memory in two weeks is harder than it looks. The tricky part is remembering the branching logic: when you hit a mismatch, try is_palindrome(left+1, right) OR is_palindrome(left, right-1). It is easy to accidentally try only one side, or to forget the helper and try to handle the deletion inline.

The opposite-end convergence building block is worth drilling until it is automatic. Once you can write a basic two pointer palindrome check without thinking, adding the "one deletion" branch on top is a small extension. You are not memorizing this specific problem. You are building a reusable skill that transfers to every converging two pointer problem.

Related posts

• Valid Palindrome - The base problem without any deletions allowed
• The Two Pointers Pattern - The foundational pattern behind the convergence approach
• Longest Palindromic Substring - A harder palindrome problem that explores all palindromic windows