Palindrome After One Deletion
mediumStrings II+20 XPTime limit 2s
A typist sometimes presses one extra key. Check whether a word is a palindrome, or can become one by deleting at most one character. abca → delete c (or b) → aba, so the answer is true. abc needs two deletions, so it is false.
Input: one line with a string of lowercase letters.
Output: true or false.
Constraints: 1 ≤ length ≤ 10⁵.
Think about it: two pointers from both ends. While the ends match, move inward. At the first mismatch you get one chance: either skip the left character or skip the right one — check whether the remaining middle part is a palindrome in either case. Trying every deletion separately would be O(n²).
Sample input 1
abca
Sample output 1
true
Sample input 2
abc
Sample output 2
false
Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).