Valid Palindrome II
Valid Palindrome II is LeetCode 680 (Easy). Given a string s of lowercase letters, return true if it can be made a palindrome when you delete at most one character.
- Deleting nothing is allowed, so a string that is already a palindrome returns true.
- The one deletion can be anywhere in the string.
s can be 100,000 characters long, so deleting each character in turn and re-checking, which is O(n²), is too slow.
- 1 <= s.length <= 10⁵
- s consists of lowercase English letters.
Intuition
Check the string from both ends as usual. While the two outer characters match, keep them: a matched pair is already correct, so there is no reason to spend the deletion on it.
At the first mismatch, s[left] and s[right] can never mirror each other, so one of these two characters must be the one deleted. That leaves exactly two candidates:
- Delete the left one: is s[left+1 .. right] a palindrome?
- Delete the right one: is s[left .. right-1] a palindrome?
Each is a plain palindrome check, with no deletions left. If either passes, the answer is true; if both fail, no single deletion can fix the string.
"Is it a palindrome if you may break the rule once" is the normal two-pointer check plus one fork. The first violation is the only place the allowance can be spent, so it branches into a small, fixed number of plain checks.
Approach
Before reading on, decide whether there is ever a reason to delete one of two ends that already match. Then, at the first mismatch, count how many different deletions are worth trying. Aim for O(n) time and O(1) extra space.
Walk inward while the ends match
Start with left = 0 and right = len(s) - 1. While s[left] == s[right], step both pointers one place in. If they meet or cross, the string is already a palindrome and no deletion is needed.
Stop at the first mismatch
When s[left] != s[right], the deletion has to remove one of these two characters, because nothing else can make this pair match. Everything outside them already matches and stays as it is.
Check both deletions
Return is_palindrome(left + 1, right) or is_palindrome(left, right - 1). The helper walks two indices inward and returns false at its first mismatch, since no deletion is left. If the first check passes, the second never runs.
Pass indices, not slices
The helper takes the two bounds of the original string instead of a slice such as s[left + 1:right + 1]. A slice copies up to n characters each time; two indices keep the extra space at O(1).
Valid Palindrome II solution in Python | C++ | Java
or stops here, so deleting the right letter is never tried.Common pitfalls
Checking only one of the two deletions
return is_palindrome(left + 1, right)
return is_palindrome(left + 1, right) or is_palindrome(left, right - 1)
On "abbca" the first mismatch is b against c. Deleting the left one leaves bc, which fails, so this code returns false. Deleting the right one leaves abba, and the answer is true.
Guessing the side from the next character
if s[left + 1] == s[right]:
left += 1
else:
right -= 1return is_palindrome(left + 1, right) or is_palindrome(left, right - 1)
Peeking one character ahead can pick the wrong side. On "abbab", s[1] equals s[4], so the guess deletes the left a, leaving bbab, which fails. Deleting the last b leaves abba, so the answer is true. Both sides have to be checked in full.
Edge cases
The pointers cross with no mismatch, so the answer is true and the deletion is never used.
Any two-letter string works: delete either letter and one character is left. The code reaches the mismatch, and the left check runs on a single character and passes.
Complexity
Valid Palindrome II FAQ
How is this different from Valid Palindrome?
Valid Palindrome (LeetCode 125) skips spaces and punctuation, ignores case and allows no deletions, so its first mismatch means false. Valid Palindrome II has only lowercase letters but allows one deletion, so its first mismatch forks into two checks instead.
Why is it safe to keep two ends that match?
Say the ends are both c and deleting the left c makes a palindrome. That palindrome starts with the next character and ends with the right c, so the next character is also c. Deleting that one instead gives the same string, keeps both ends, and is found by the walk inward.
What if up to k deletions were allowed?
Forking at every mismatch can double the work each time. That version is Valid Palindrome III (LeetCode 1216), solved with dynamic programming: find the longest palindromic subsequence, and the answer is true when the characters outside it number at most k.