Loading page…
Practice problem · medium
A search app has a word game. When a player types a query, the app checks whether it reads the same forwards and backwards. Players often type one extra letter by mistake.
To be forgiving, the app accepts a query if it is a palindrome after removing at most one letter. You are asked to write that check for lower-case queries, and it must be fast for long pasted text.
Write almost_palindrome(query).
query is a string of lower-case letters.true if the remaining letters read the same forwards and backwards for some choice, and false otherwise.Input: query = "abca"
Output: truePointers lo and hi walk inward while the letters match. At the first mismatch, the check tries to remove either letter.
| lo | hi | Letters | Result |
|---|---|---|---|
| 0 | 3 | a and a | match: both pointers move in |
| 1 | 2 | b and c | the first mismatch |
At the mismatch, remove the left letter and check the stretch 2 to 2, which is c. A single letter is a palindrome, so the answer is true. (Removing the right letter and checking b also works.)
Input: query = "abcde"
Output: falseAfter the first mismatch, a and e, removing either one leaves bcde or abcd. Neither is a palindrome.
Input: query = "zz"
Output: trueIt is a palindrome already, so nothing needs to be removed.
1 ≤ query.length ≤ 100,000 (a long pasted query)query holds the lower-case letters a to zRemoving each letter in turn and checking the rest costs about n × n ÷ 2 steps. That is 5 × 10^9 at n = 100,000, about 50 seconds at 10^8 operations a second. A walk that stops at the first mismatch and makes two final checks costs at most about 2n steps, 200,000 at n = 100,000.
almost_palindrome · runs in your browserCoding is easiest on a laptop. On a phone, read, trace and try small edits.