Valid Palindrome II
Valid Palindrome II: return true if the string can be made a palindrome after deleting at most one character.
- 1 <= s.length <= 10⁵
- s consists of lowercase English letters.
Intuition
Walk inward from both ends while the characters match — those pairs are already settled and can never be the problem. The first mismatch is the only place a deletion could ever help, and there are exactly two candidates: drop the left character or drop the right one. Test both; if either remaining stretch is a plain palindrome, the answer is yes.
This is the 'one exception allowed' variant of a two-pointer scan. The shape recurs: run the ordinary check, and at the first violation branch into the small set of repairs the budget permits. Because matching pairs are forced, no backtracking or DP is needed — recognise that the first conflict is the only decision and the O(n) solution falls out.
Approach
Before reading on: if the ends already match, is there ever a reason to delete one of them? And when they disagree, how many genuinely different choices do you have? Aim for O(n) time and O(1) space.
Matching pairs need no decision
Two pointers start at the ends and move toward each other. While s[left] == s[right], that pair is consistent with a palindrome no matter what happens elsewhere, so there is nothing to decide and no reason to spend the deletion. Advancing past them is free. If the pointers cross without ever disagreeing, the string was already a palindrome and the answer is true with the deletion unused.
The first mismatch is the only decision point
When s[left] != s[right], a palindrome is impossible unless one of these two characters goes. Deleting anything strictly inside the window cannot fix this specific pair, and deleting anything outside it is impossible — those characters are already matched. So the entire problem reduces to two candidate substrings: s[left+1 .. right] (drop the left char) and s[left .. right-1] (drop the right char). This is why the algorithm is greedy: the first conflict forces the choice, and there is never a second one to spend.
Verify each candidate with a plain palindrome check
Because the budget is exactly one deletion, once you have used it the remainder must be a palindrome outright. Run an ordinary two-pointer equality check on each of the two candidates and return true if either passes. The scan to the first mismatch is O(n), and each verification is O(n), so the total stays O(n) time with O(1) extra space — no copying is needed if the helper takes index bounds instead of slices.
Solution & live demo
Common pitfalls
Returning false at the first mismatch
if s[left] != s[right]:
return Falseif s[left] != s[right]:
return is_pal(left + 1, right) or is_pal(left, right - 1)That is the Valid Palindrome I logic. Here a mismatch is not fatal — it is precisely where the one allowed deletion gets spent, so it must branch instead of rejecting.
Testing only one side of the deletion
return is_pal(left + 1, right)
return is_pal(left + 1, right) or is_pal(left, right - 1)
Both deletions must be tried. On "abca" dropping the left character gives bca (not a palindrome) while dropping the right gives aba (a palindrome); checking one side alone reports false on a valid input.
Allowing more than one deletion via recursion
def check(i, j, used):
...
return check(i+1, j, used+1) or check(i, j-1, used+1)return is_pal(left + 1, right) or is_pal(left, right - 1)
Recursing with a counter re-opens the branch at every later mismatch, giving exponential work and, if the budget is mishandled, wrong answers on strings needing two deletions. After the single deletion the rest must be a strict palindrome — use the plain check.
Edge cases
The pointers cross with no mismatch, so it returns true without using the deletion.
The loop body never runs; both are trivially palindromes and return true.
Dropping 'b' fails but dropping 'c' succeeds, so testing both candidates is essential.
Neither candidate is a palindrome, so it correctly returns false.
Pointers meet without overlapping; the crossing condition left < right terminates cleanly.