680. Valid Palindrome II

At a Glance

Topic: two-pointers
Pattern: Two Pointers + single skip
Difficulty: Easy
Companies: Amazon, Facebook, Uber, Bloomberg, Adobe
Frequency: Medium
LeetCode: 680

Problem (one-liner)

Given a string s, return true if it can be a palindrome after deleting at most one character; otherwise false.

Recognition Cues

"Almost palindrome" / one deletion allowed
Mismatch at (left, right) → try skipping left OR skipping right
Two-phase palindrome check

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Loading diagram…

Approaches

Brute force — try deleting each index — O(n²) time.
Better — two pointers with recursion or helper on mismatch — O(n) time / O(n) stack worst case.
Optimal — two pointers; on first mismatch, verify palindrome(left+1, right) OR palindrome(left, right-1) — O(n) time / O(1) space.

Optimal Solution

Go

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

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

JavaScript

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

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