455. Valid Palindrome II
You receive a string s of lowercase English letters. Decide whether s can be made into a palindrome by deleting at most one character — deleting zero characters is fine, deleting two is not.
Return true if it is possible and false otherwise.
Example 1:
Input: s = "aba"
Output: true
Explanation: Already a palindrome — zero deletions needed.
Example 2:
Input: s = "abca"
Output: true
Explanation: Delete the 'c' (or the 'b') to get "aba".
Example 3:
Input: s = "abc"
Output: false
Explanation: One deletion leaves "bc", "ac" or "ab" — none is a palindrome.
Constraints:
- 1 ≤ s.length ≤ 10⁵
- s consists of lowercase English letters
Hints:
A correct slow plan: for each index, delete it and test whether the rest reads the same backwards — O(n²). Where is the wasted work? Most deletions can't possibly matter.
March two pointers inward from both ends. All the pairs they match are already fine; at the FIRST mismatch, the character you delete must be one of the two under the pointers. Test both skips with a plain palindrome check on the remaining window — that's the whole algorithm, O(n).
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: s = "aba"
Expected output: true