Skills101
← All coding problems

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).

Loading editor…

Log in to run and submit your code — it's free.