LeetCode 680 — Valid Palindrome II | Full Solution Explained

Difficulty	Pattern	Asked At	LeetCode Link
Easy	Two Pointers	Facebook, Amazon, Google, Microsoft	leetcode.com/problems/valid-palindrome-ii

📌  This problem is a direct follow-up to LeetCode 125 — Valid Palindrome. If you haven’t read that post yet, start there — it covers the Two Pointers palindrome template that this problem builds on.

Valid Palindrome II is one of those problems that looks straightforward until you start thinking about the edge cases.

‘Just try removing each character one by one and check if the result is a palindrome’ — that’s the first idea almost everyone gets. It works. But it’s O(n²) and will TLE on large inputs.

The optimal solution is O(n) and elegant — once you understand the key insight. The tricky part is not the code itself, it’s knowing WHEN to try skipping a character and WHICH character to skip.

That’s exactly what this post focuses on.

The Problem Statement

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

Example

Example 1:
  Input:  s = "aba"
  Output: true
  Why:    Already a palindrome — no deletion needed.
 
Example 2:
  Input:  s = "abca"
  Output: true
  Why:    Delete 'c' → "aba" which is a palindrome.
          OR delete 'b' → "aca" which is also a palindrome.
 
Example 3:
  Input:  s = "abc"
  Output: false
  Why:    No single deletion makes it a palindrome.
          Remove 'a' → "bc"  — not palindrome
          Remove 'b' → "ac"  — not palindrome
          Remove 'c' → "ab"  — not palindrome

Key Constraints

Constraint	What it means for us
1 <= s.length <= 100,000	Large input — O(n²) brute force will TLE, need O(n)
s consists only of lowercase letters	No special characters — no need to filter like LC 125
At most ONE deletion allowed	We get exactly one ‘skip’ — use it wisely

💡  Unlike LeetCode 125, this problem has ONLY lowercase letters — no spaces, no punctuation. You do NOT need to skip non-alphanumeric characters here. Every character counts.

Step 1 — Brute Force Approach (O(n²))

The simplest idea: try removing each character one at a time and check if the resulting string is a palindrome.

Bruteforce

// Brute Force — O(n²) time, O(n) space
bool validPalindrome(string s) {
    int n = s.length();
 
    // helper to check if a string is palindrome
    auto isPalin = [](string& str, int l, int r) {
        while (l < r) {
            if (str[l] != str[r]) return false;
            l++; r--;
        }
        return true;
    };
 
    // try removing each character one by one
    for (int i = 0; i < n; i++) {
        string modified = s.substr(0, i) + s.substr(i + 1);
        if (isPalin(modified, 0, modified.length() - 1)) {
            return true;
        }
    }
    return false;
}

Metric	Brute Force	Problem
Time Complexity	O(n²)	n iterations × O(n) palindrome check = O(n²)
Space Complexity	O(n)	Creates a new string for each deletion
LeetCode Result	TLE	Fails for strings of length 100,000

⚠️  For n = 100,000 characters, brute force makes 100,000 × 100,000 = 10 billion character comparisons. That’s way past the time limit. We need to be smarter.

Step 2 — The Key Insight

Let’s think about what actually happens when we use Two Pointers on this problem.

We start with left = 0 and right = n – 1 and move inward, comparing characters.

As long as s[left] == s[right], everything is fine — keep moving inward.

The interesting moment is when we hit a MISMATCH: s[left] != s[right].

🤔  When we find s[left] != s[right], we need to use our one allowed deletion. But which character should we delete — the left one or the right one?

Here’s the key insight: we don’t know which one to skip. So we try BOTH options:

• Option A: Skip the LEFT character — check if s[left+1 .. right] is a palindrome
• Option B: Skip the RIGHT character — check if s[left .. right-1] is a palindrome

🔑  If EITHER of those two substrings is a palindrome → return true. If NEITHER is → return false. We only ever need to make this decision ONCE — at the first mismatch. After that, no more deletions are allowed.

This is what makes the solution O(n) instead of O(n²). We don’t try all n possible deletions — we only try the 2 possible skips at the exact point where the first mismatch occurs.

Step 3 — Full Dry Runs (Trace Every Step)

Let’s trace through multiple examples to make sure the insight is completely clear.

Dry Run 1 — “abca” (expected: true)

s = "abca"
     a  b  c  a
idx: 0  1  2  3
 
left = 0, right = 3

Step	left	right	s[left]	s[right]	Match?	Action
1	0	3	a	a	YES	Move both inward → left=1, right=2
2	1	2	b	c	NO	MISMATCH! Try both options:
						Option A: skip left → check s[2..2] = ‘c’ — palindrome? YES
						Option B: skip right → check s[1..1] = ‘b’ — palindrome? YES
Result						Option A is palindrome → return TRUE

✅  Answer: true. We found a mismatch at step 2, tried both options, and both work. Return true.

Dry Run 2 — “abc” (expected: false)

s = "abc"
     a  b  c
idx: 0  1  2
 
left = 0, right = 2

Step	left	right	s[left]	s[right]	Match?	Action
1	0	2	a	c	NO	MISMATCH! Try both options:
						Option A: skip left → check s[1..2] = ‘bc’ — is ‘bc’ palindrome? NO
						Option B: skip right → check s[0..1] = ‘ab’ — is ‘ab’ palindrome? NO
Result						Neither works → return FALSE

✅  Answer: false. Both options at the first mismatch fail the palindrome check.

Dry Run 3 — Tricky Case: “aguokepatgbnvfqmgmlcupuufxoohdfpgjdmysgvhmvffcnqxjjxqncffvmhvgsymdjgpfdhooxfuupuculmgmqfvnbgtapekouaga”

This is a long string — too long to trace fully. But let’s understand the pattern. The pointers meet correctly in the middle as long as characters match. The one mismatch gets resolved by trying both skips.

The important thing to understand: no matter how long the string, the algorithm only does ONE pass with the two pointers, plus ONE additional palindrome check on a substring when the mismatch is found. That’s still O(n).

Dry Run 4 — The Trickiest Case: “deeee” (expected: true)

This case catches many beginners. Watch carefully.

s = "deeee"
     d  e  e  e  e
idx: 0  1  2  3  4
 
left = 0, right = 4

Step	left	right	s[left]	s[right]	Match?	Action
1	0	4	d	e	NO	MISMATCH at the very first step! Try both:
						Option A: skip left → check s[1..4] = ‘eeee’ — palindrome? YES
						Option B: skip right → check s[0..3] = ‘deee’ — palindrome? NO
Result						Option A is palindrome → return TRUE

✅  Answer: true. We skip ‘d’ (the left character) and the remaining ‘eeee’ is a palindrome.

💡  The mismatch can happen at the very first step (like here). That’s perfectly fine — we still try both options and return true if either works.

Step 4 — The Optimal Solution

Now the code. The helper function isPalindromeRange is the key — it checks if a substring from index l to r is a palindrome without creating a new string.

C++ Solution

#include <string>
using namespace std;
 
class Solution {
public:
 
    // helper: check if s[l..r] is a palindrome
    bool isPalindromeRange(const string& s, int l, int r) {
        while (l < r) {
            if (s[l] != s[r]) return false;
            l++;
            r--;
        }
        return true;
    }
 
    bool validPalindrome(string s) {
        int left  = 0;
        int right = s.length() - 1;
 
        while (left < right) {
 
            if (s[left] != s[right]) {
                // MISMATCH found — try both possible skips
                // Option A: skip left character, check s[left+1 .. right]
                // Option B: skip right character, check s[left .. right-1]
                return isPalindromeRange(s, left + 1, right) ||
                       isPalindromeRange(s, left, right - 1);
            }
 
            // characters match — move both pointers inward
            left++;
            right--;
        }
 
        // no mismatch found — already a palindrome
        return true;
    }
};

Python Solution

class Solution:
    def validPalindrome(self, s: str) -> bool:
 
        def is_palindrome_range(l: int, r: int) -> bool:
            # helper: check if s[l..r] is a palindrome
            while l < r:
                if s[l] != s[r]:
                    return False
                l += 1
                r -= 1
            return True
 
        left  = 0
        right = len(s) - 1
 
        while left < right:
 
            if s[left] != s[right]:
                # MISMATCH found — try both possible skips
                # Option A: skip left  → check s[left+1 .. right]
                # Option B: skip right → check s[left .. right-1]
                return is_palindrome_range(left + 1, right) or                        is_palindrome_range(left, right - 1)
 
            # characters match — move both pointers inward
            left  += 1
            right -= 1
 
        # no mismatch found — already a palindrome
        return True

JavaScript Solution

/**
 * @param {string} s
 * @return {boolean}
 */
var validPalindrome = function(s) {
 
    // helper: check if s[l..r] is a palindrome
    const isPalindromeRange = (l, r) => {
        while (l < r) {
            if (s[l] !== s[r]) return false;
            l++;
            r--;
        }
        return true;
    };
 
    let left  = 0;
    let right = s.length - 1;
 
    while (left < right) {
 
        if (s[left] !== s[right]) {
            // MISMATCH found — try both possible skips
            // Option A: skip left  → check s[left+1 .. right]
            // Option B: skip right → check s[left .. right-1]
            return isPalindromeRange(left + 1, right) ||
                   isPalindromeRange(left, right - 1);
        }
 
        // characters match — move both pointers inward
        left++;
        right--;
    }
 
    // no mismatch found — already a palindrome
    return true;
};

Step 5 — Complexity Analysis

Metric	Brute Force	Two Pointers (Optimal)	Why
Time	O(n²)	O(n)	One outer pass + one inner palindrome check of length ≤ n = O(n) total
Space	O(n)	O(1)	No new strings created — only 4 integer variables (left, right, l, r)

Why Is It O(n) and Not O(2n)?

The outer while loop scans at most n/2 steps. When a mismatch is found, isPalindromeRange scans at most n more characters. That’s O(n/2) + O(n) = O(n) total. We drop constants in Big O notation, so it’s just O(n).

🚀  The key insight that makes this O(n): we only call isPalindromeRange ONCE — at the first mismatch. We never call it multiple times. This is why the approach is optimal.

Step 6 — Why Don’t We Need to Try All Possible Deletions?

This is the question most people have after seeing the solution. Why is it correct to only try the 2 options at the first mismatch? What if the optimal deletion is somewhere in the middle of the string?

🤔  Could it be that the first mismatch is NOT the right place to use our deletion, and a later mismatch would have been better?

The answer is no — and here’s why.

All characters before the first mismatch already match their mirror. So deleting any of those characters would break an existing match — it would make the palindrome worse, not better.

The first mismatch is the first character that doesn’t fit. So our one deletion must be used on one of the two characters involved in that mismatch — either the left one or the right one. Those are the only two candidates.

If skipping either of them results in a palindrome, great. If neither works, no single deletion anywhere in the string can save it.

🔑  This greedy argument — use the deletion at the first mismatch, try both options — is what makes the O(n) solution provably correct. Not just fast, but mathematically correct.

Step 7 — Common Mistakes Beginners Make

Mistake 1 — Using Substring or String Slicing in the Helper

Some people write the helper as: return s.substr(l, r-l+1) == reverse(s.substr(l, r-l+1)). This works but creates new strings — O(n) space per call. Use the two-pointer helper with indices instead. It checks in-place with O(1) space.

Mistake 2 — Calling the Helper Recursively After a Second Mismatch

A very common wrong approach: when you find a mismatch in the helper, call the helper again with another skip. This is wrong — you only get ONE total deletion across the entire problem. The main function uses it at the first mismatch. The helper must check a clean palindrome with NO further skips allowed.

⚠️  The helper isPalindromeRange is a STRICT palindrome check — no deletions allowed inside it. Only the outer validPalindrome function gets to use the one skip.

Mistake 3 — Checking Only One Option Instead of Both

Some people write: return isPalindromeRange(s, left+1, right). They only try skipping the left character. This misses cases where skipping the right character is the correct move. ALWAYS check both options with OR.

Mistake 4 — Forgetting the Already-Palindrome Case

If the entire string has no mismatches — it’s already a palindrome — the while loop completes without returning early, and we must return true at the end. Don’t forget the final return true after the loop.

Step 8 — Edge Cases

Edge Case	Input	Output	Reason
Single character	“a”	true	One char is always a palindrome
Two same characters	“aa”	true	Already a palindrome
Two different characters	“ab”	true	Delete either one → single char = palindrome
Already palindrome	“racecar”	true	No mismatch found → return true
One char off, start	“deeee”	true	Skip ‘d’ → ‘eeee’ is palindrome
One char off, middle	“abcba”	true	Already palindrome — wait, ‘abcba’ is already ok
One char off, middle	“abccba”	true	Already palindrome
Two chars off	“abcdef”	false	Need 3+ deletions — impossible with just 1
Mismatch needs both tried	“abca”	true	Skip ‘b’ → ‘aca’ OR skip ‘c’ → ‘aba’ — both work

✅  Our solution handles every edge case correctly. The two-character case (‘ab’) is interesting — skip either character, you get a single character left, which is always a palindrome.

Valid Palindrome I vs Valid Palindrome II — Complete Comparison

Feature	LC 125 — Valid Palindrome	LC 680 — Valid Palindrome II
Input characters	Any characters (letters, digits, spaces, punctuation)	Only lowercase letters a-z
Filtering needed?	YES — skip non-alphanumeric, convert to lowercase	NO — every character counts
Deletion allowed?	NO — just check as-is after filtering	YES — at most ONE character
Core challenge	Skipping invalid chars correctly	Deciding which char to skip on mismatch
Pattern	Two Pointers with character skipping	Two Pointers with one-skip helper
Time complexity	O(n)	O(n)
Space complexity	O(1)	O(1)

📌  LeetCode 680 is actually simpler to code than LeetCode 125 — no character filtering needed. The challenge is purely the logic of handling the one allowed deletion correctly.

Step 9 — How to Explain This in an Interview

This problem appears frequently at Facebook and Amazon for software engineering roles. Here’s the exact walkthrough:

• Step 1 — Clarify: ‘We can delete at most one character. The string has only lowercase letters. Correct?’
• Step 2 — Brute force: ‘Naive approach: try removing each of n characters and check if result is palindrome — O(n²). Too slow for n=100,000.’
• Step 3 — Insight: ‘Use Two Pointers. Move inward while characters match. At the first mismatch, we must use our one deletion. We try skipping the left character OR the right character and check if either remaining substring is a palindrome.’
• Step 4 — Why only two options: ‘Everything before the mismatch already matches. So the deletion must be at the mismatch point. Only two candidates — the left or right character involved in the mismatch.’
• Step 5 — Dry run: Trace ‘abca’ showing the mismatch at index 1 and 2, then both checks.
• Step 6 — Code: Write the outer Two Pointers loop and the isPalindromeRange helper.
• Step 7 — Complexity: ‘O(n) time — one pass plus at most one O(n) helper call. O(1) space — no new strings.’
• Step 8 — Edge cases: Single char, already palindrome, mismatch at very first step.

💡  The interviewer is specifically testing whether you understand WHY only two options need to be tried. If you just say ‘try both and see’ without explaining the greedy argument, they’ll probe deeper. Explain that characters before the first mismatch already match, so the deletion must happen at the mismatch point.

Final Solution at a Glance

C++ Solution

class Solution {
public:
    bool isPalindromeRange(const string& s, int l, int r) {
        while (l < r) {
            if (s[l] != s[r]) return false;
            l++; r--;
        }
        return true;
    }
 
    bool validPalindrome(string s) {
        int left = 0, right = s.length() - 1;
        while (left < right) {
            if (s[left] != s[right]) {
                return isPalindromeRange(s, left + 1, right) ||
                       isPalindromeRange(s, left, right - 1);
            }
            left++; right--;
        }
        return true;
    }
};

Time Complexity	Space Complexity	LeetCode Result	Difficulty
O(n)	O(1)	Accepted ✓	Easy

Wrapping Up

Valid Palindrome II is a beautiful upgrade from Valid Palindrome I. It takes the same Two Pointers template and adds one twist — handle a mismatch by trying both possible skips.

The three things to lock in from this problem:

• Use the outer Two Pointers as normal — move inward while characters match
• At the FIRST mismatch, try BOTH options: skip left OR skip right
• The helper isPalindromeRange must be a strict check — no further skips inside it

Once this pattern is clear, you’ll recognise it in similar problems — like checking if a string can become a palindrome with k deletions (a harder generalization of this exact problem).

📬  This is part of the Two Pointers series on Daily Dev Notes. Next up: LeetCode 15 — 3Sum. It uses Two Pointers inside a for loop — a step up in difficulty but completely doable. Subscribe so you don’t miss it.

Got a question about any step or edge case? Drop it in the comments — I reply to every one.