Valid Palindrome II — Delete At Most One Character [LC 680, Facebook, Amazon]

Problem Statement#

LeetCode 680 — Valid Palindrome II · Difficulty: Easy/Medium

Given a string s, return true if the s can be made a palindrome by removing at most one character from it.

Constraints:

• 1 <= s.length <= 10^5
• s consists only of lowercase English letters

Example 1:

Input:  s = "aba"
Output: true
Explanation: Already a palindrome — no deletion needed.

Example 2:

Input:  s = "abca"
Output: true
Explanation: Delete 'c' → "aba", which is a palindrome.

Example 3:

Input:  s = "abc"
Output: false
Explanation: Deleting any single character ("bc", "ac", "ab") is not a palindrome.

Why This Problem Matters#

LC 680 is the standard greedy two-pointer with one skip problem. Facebook (Meta) asks it frequently in phone screens because it tests whether candidates can extend a simple palindrome check with a controlled "branch and check both options" decision. The solution is elegant: two pointers collapse toward the center; at the first mismatch, try skipping left, try skipping right, and return whether either option yields a palindrome.

The problem matters because it establishes the pattern for harder "almost-palindrome" problems (LC 1216, LC 2330) and for any problem where a single allowed modification needs to be handled greedily. The insight — "skip left XOR skip right, never both" — is the template.

The easy mistake is trying to greedily decide which character to skip at the first mismatch. You cannot know which skip is correct without checking both options.

The Core Insight#

Use two pointers l and r starting at each end. Move them inward while characters match. When a mismatch occurs at (l, r):

• Option A: skip s[l], check if s[l+1 .. r] is a palindrome.
• Option B: skip s[r], check if s[l .. r-1] is a palindrome.

Return true if either option yields a palindrome.

The key insight: once we encounter the first mismatch, we have used our one allowed deletion. The remaining substring (whichever option we choose) must be a strict palindrome — no more deletions allowed. So the helper function is_palindrome(l, r) is a simple O(n) check.

If no mismatch is encountered before l >= r, the string is already a palindrome and we return true (zero deletions used).

Visual Dry Run#

Input: s = "abca" (indices 0-3)

l=0, r=3: s[0]='a', s[3]='a' → match, l=1, r=2
l=1, r=2: s[1]='b', s[2]='c' → MISMATCH
  Option A: is_palindrome("c") = s[2..2] → true  ✓
  → return true

Input: s = "eeccccbebaeeabebccceea" (a harder case)

Two pointers march inward matching 'e','e','c','c','c','b' ...
On first mismatch, branch:
  Option A: check s[l+1..r] → not palindrome
  Option B: check s[l..r-1] → palindrome  ✓
→ return true

Common Mistakes#

1. Trying to decide which character to skip without checking both options. At the mismatch (l, r), it is not always obvious which skip leads to a palindrome. You must try both and return true if either works.

2. Calling is_palindrome recursively with another skip allowed. After the first skip, the remaining substring must be a strict palindrome — no more deletions. Passing a "remaining skips" counter and allowing a second skip gives a wrong answer for some inputs.

3. Checking only is_palindrome(s[l+1..r]) or only is_palindrome(s[l..r-1]). Missing one of the two options causes failures on inputs where only the other option yields a palindrome.

4. Off-by-one in the helper function. is_palindrome(l+1, r) should check s[l+1 .. r] inclusive. Using exclusive right bound or wrong indices produces wrong results.

5. Not handling the case where the string is already a palindrome. If all characters match (no mismatch encountered), the function should return true. This is handled by the loop completing without hitting the mismatch branch.

6. Performance issue: slicing the string. In Python, is_palin(s[l+1:r+1]) creates a new string O(n). Pass index boundaries instead to avoid O(n) allocations in the helper.

Solutions#

Python#

def validPalindrome(s: str) -> bool:
    def is_palindrome(l: int, r: int) -> bool:
        """Check if s[l..r] inclusive is a strict palindrome."""
        while l < r:
            if s[l] != s[r]:
                return False
            l += 1
            r -= 1
        return True
 
    l, r = 0, len(s) - 1
 
    while l < r:
        if s[l] != s[r]:
            # First mismatch: try skipping left character OR skipping right character
            return is_palindrome(l + 1, r) or is_palindrome(l, r - 1)
        l += 1
        r -= 1
 
    # No mismatch found — already a palindrome
    return True

JavaScript#

function validPalindrome(s) {
    function isPalindrome(l, r) {
        // Check if s[l..r] inclusive is a strict palindrome (no deletions allowed)
        while (l < r) {
            if (s[l] !== s[r]) return false;
            l++;
            r--;
        }
        return true;
    }
 
    let l = 0;
    let r = s.length - 1;
 
    while (l < r) {
        if (s[l] !== s[r]) {
            // First mismatch: try both skip options
            return isPalindrome(l + 1, r) || isPalindrome(l, r - 1);
        }
        l++;
        r--;
    }
 
    return true;  // string is already a palindrome
}

Complexity Analysis#

The main loop runs at most n/2 steps before finding a mismatch (or completing). At the mismatch, we call is_palindrome at most twice, each O(n). Total: O(n). Space is O(1) — only pointer variables, no string copies (when using index-based helper).

Follow-up Questions#

1. LC 125 — Valid Palindrome: Ignoring non-alphanumeric characters, check strict palindrome. No deletions allowed. Two pointers, skip non-alphanumeric.

2. LC 1216 — Valid Palindrome III (at most k deletions): Generalize to allow k deletions. Requires dynamic programming: dp[l][r] = minimum deletions to make s[l..r] a palindrome. O(n²) time and space.

3. What if you need to return the resulting palindrome (not just true/false)? When is_palindrome(l+1, r) returns true, the palindrome is s[:l] + s[l+1:]. When is_palindrome(l, r-1) returns true, it is s[:r] + s[r+1:].

4. What if there are two mismatches? With at most one deletion, two mismatches mean it's impossible. With at most two deletions (LC 1216 with k=2), use DP.

This Pattern Solves#

• LC 680 — Valid Palindrome II (this problem, one deletion)
• LC 125 — Valid Palindrome (no deletion, skip non-alphanumeric)
• LC 1216 — Valid Palindrome III (at most k deletions, DP)
• LC 2330 — Valid Palindrome IV (at most two swaps)
• Any "is this sequence almost-X" problem where "almost" means one operation

Key Takeaways#

• LC 680 is asked by Facebook and Amazon to test the "greedy with branch" two-pointer pattern: march inward matching characters, then at the first mismatch try both options.
• At the first mismatch (l, r), the two options are: skip left (is_palindrome(l+1, r)) or skip right (is_palindrome(l, r-1)); return true if either works.
• After the first skip, no more deletions are allowed — the helper is_palindrome(l, r) checks a strict palindrome with no extra branches.
• You cannot greedily decide which character to skip at the mismatch — you must try both; either or both or neither option may work.
• Always use index-based helper calls (is_palindrome(l+1, r)) instead of string slicing to avoid O(n) allocation per call.
• If the outer loop completes without a mismatch, the string is already a palindrome — return true (zero deletions used is within the budget).
• Time O(n), space O(1) — the algorithm does at most three linear scans of the string total.