Return true if the string can be a palindrome after deleting at most one character.
DSA Animator › DSA Revision › Strings › Valid Palindrome II
Remember: one deletion allowed means two choices at the first mismatch. Check both, each in linear time. The video solves Valid Palindrome II (LeetCode 680, Medium) with the Two Pointers pattern from the Strings topic, and you can replay every step in the interactive Valid Palindrome II animation.
Return true if the string can be a palindrome after deleting at most one character.
For a b c a, the answer is true. Deleting either b or c leaves a palindrome.
Trying to delete every character, then checking, is O of n squared. Only the first mismatch matters.
Compare characters from both ends with two pointers. At the first mismatch, you have exactly two options: skip the left character, or skip the right one. If either remaining part is a palindrome, the answer is true.
a and a match, so move both pointers inward. b and c do not match. Skipping b leaves c, which is a palindrome. So the answer is true.
In code, move inward while the characters match. At a mismatch, return whether the range without the left character, or without the right character, is a palindrome. A helper checks a range with two pointers. Everything is linear, so it's O of n time and O of 1 space.
Remember: one deletion allowed means two choices at the first mismatch. Check both, each in linear time.