visual walkthrough
Valid Palindrome II
Allows one deletion, so you learn to branch once and re-check; a Meta favourite.
The idea
Walk inward from both ends exactly as in the plain palindrome check. Only at the first mismatch do you need a decision: the extra letter is either the left one or the right one.
Check whether the remaining middle is a palindrome with the left letter skipped, and again with the right one skipped. If either works, the answer is true.
Complexity
| approach | time | space |
|---|---|---|
| Try every deletion | O(n²) | O(n) |
| Two pointers | O(n) | O(1) |