680. Valid Palindrome II

Quick Identifier

Topic: two-pointers
Pattern: inward convergence with one allowed deletion
Difficulty: Easy
Companies: Amazon, Facebook, Uber, Bloomberg, Adobe
Frequency: Medium
LeetCode: 680
Hint: At the first mismatch, try skipping left or skipping right exactly once.

Quick Sights

Time Complexity: O(n) - the remaining window is checked at most twice.
Space Complexity: O(1) - use indexes, not substring copies.
Core Mechanism: Run normal palindrome scan. On first mismatch, return whether either remaining window is a strict palindrome.

Concept Explanation

Before the first mismatch, all outside pairs are already valid. At the mismatch, one deletion means there are only two possible repairs: delete the left character or delete the right character.

After spending that deletion, the rest must be a normal palindrome. No deeper recursion is needed because the deletion budget is one.

Diagram

This diagram shows the pointer decisions and the step-by-step algorithm flow.

Loading diagram…

Study Pattern (SDE3+)

0-3 min: Name the pointer shape, then state the invariant and discard rule before coding.
Implementation pass: Keep pointer movement explicit; every branch must return, record an answer, or move at least one pointer.
5 min extension: Explain how the solution changes for immutable input, streaming input, many duplicate values, or many repeated queries.

Approaches

Deleting each index is O(n^2). Two pointers branch once at the first mismatch and stay O(n).

Optimal Solution

JavaScript

function validPalindrome(s) {
	let left = 0, right = s.length - 1;
	while (left < right) {
		if (s[left] === s[right]) {
			left++;
			right--;
		} else {
			return isPalindromeRange(s, left + 1, right) || isPalindromeRange(s, left, right - 1);
		}
	}
	return true;
}

function isPalindromeRange(s, left, right) {
	while (left < right) {
		if (s[left++] !== s[right--]) return false;
	}
	return true;
}

Go

func validPalindrome(s string) bool {
	left, right := 0, len(s)-1
	for left < right {
		if s[left] == s[right] {
			left++
			right--
		} else {
			return isPalindromeRange(s, left+1, right) || isPalindromeRange(s, left, right-1)
		}
	}
	return true
}

func isPalindromeRange(s string, left int, right int) bool {
	for left < right {
		if s[left] != s[right] { return false }
		left++
		right--
	}
	return true
}