Valid Palindrome II: One Deletion, Two Branches

"Valid Palindrome II" shows up again and again in Meta, Amazon, Microsoft phone screens. It is a Easy problem on paper, but the real test is whether you recognize the Two Pointers pattern quickly and code it cleanly. Part 11 of 12 in the Two Pointers arc.

The Problem

Given a string s, return True if it can be a palindrome after deleting at most one character. Meta reportedly asks this more than almost any other string question, because the clean answer requires resisting brute force n-deletions.

Input:  s = "abca"
Output: True
Delete "b" or "c" and the rest is a palindrome.

Recognizing the Two Pointers Pattern

Two pointers means walking a sequence with two indices that move based on a comparison — from both ends inward, or slow-and-fast in one direction. It turns brute-force pair scans that cost O(n²) into a single O(n) pass, and it is usually the intended answer whenever the input is sorted or can be sorted cheaply.

Converging pointers with a budget: scan as usual, and only at the first mismatch does the single deletion matter. There are exactly two repair options — drop the left char or drop the right — so the branch factor is 2, once, not n.

The Approach

Run the standard palindrome scan. On mismatch at positions i and j, the answer is whether s[i+1..j] or s[i..j-1] is a clean palindrome — check both with a budget-free helper and OR the results.

Total work: at most one full scan plus two partial scans. The same structure generalizes to k deletions with recursion and memoization, which is the standard follow-up.

Python Solution

def valid_palindrome_ii(s: str) -> bool:
    """True if s is a palindrome after deleting at most one char."""

    def is_pal(i: int, j: int) -> bool:
        while i < j:
            if s[i] != s[j]:
                return False
            i += 1
            j -= 1
        return True

    i, j = 0, len(s) - 1
    while i < j:
        if s[i] != s[j]:
            return is_pal(i + 1, j) or is_pal(i, j - 1)
        i += 1
        j -= 1
    return True

Complexity

• Time: O(n) — one main scan plus at most two sub-scans of the middle section
• Space: O(1) — helper works on indices of the original string, no slicing

Interview Tips and Follow-Ups

• Avoid Python slicing (s[i+1:j+1][::-1]) in the helper — it silently costs O(n) space per call and interviewers notice.
• Generalize to k deletions: recursion on (i, j, k) with memoization — say it maps to edit-distance-style DP.
• Why check both branches? A greedy choice of which side to delete fails on cases like "cbbcc" — have a counterexample ready.

More Two Pointers problems — and the other eight patterns — live in the Technical Interview category. Drill the pattern, not the problem: that is the entire thesis of this series.