613. Almost a Palindrome

A lowercase word is given. Print Yes if it reads the same forwards and backwards after deleting AT MOST ONE character, and No otherwise.

Deleting nothing is allowed, so a word that is already a palindrome answers Yes.

aba -> Yes already a palindrome abca -> Yes delete c abc -> No

## Why trying every deletion is too slow

Deleting each character and testing the result is O(n^2), which at n = 200000 is 4 * 10^10 character comparisons. The sweep below is O(n).

## There is only one decision to make

Walk inward from both ends. While the characters match, nothing has been spent and there is nothing to decide.

At the FIRST mismatch, at positions i and j, exactly one deletion is available and it must be used here: every earlier pair already matched, so deleting anything outside i..j would break one of those pairs and leave this mismatch unrepaired.

Two repairs are possible: drop s[i], or drop s[j]. Check whether s[i+1..j] is a palindrome, or s[i..j-1] is. If either holds, answer Yes.

while i < j: if s[i] != s[j]: return isPalindrome(i+1, j) or isPalindrome(i, j-1) i += 1; j -= 1 return Yes

## Why one mismatch is all you ever examine

Each of the two checks is a plain palindrome test with no deletions left, so neither can recurse. The whole algorithm therefore does at most one extra linear pass, which is why it stays O(n) rather than becoming O(n^2).

If neither repair works, the answer really is No: those were the only two things a single deletion could have done at this position, and the deletion had to happen at this position.

## Boundaries

A single character answers Yes. Any two characters answer Yes, since deleting one leaves a single character.

abc is the shortest No. Both repairs fail: removing a leaves bc and removing c leaves ab.

abcd is also No, and is worth keeping because a solution that only checks one of the two repairs may pass abc by luck and fail here.

## Cost

Time O(n). Space O(1).

Constraints - `1 ≤ length ≤ 200000` - the word contains only lowercase letters