Loading...
Loading...
Loading...
A word is given. Delete some letters, keeping the order of the rest, so that what remains reads the same backwards. Print the greatest possible length of what remains.
Example 1
Input
bbbab
Output
4
Delete the a to get bbbb.
Example 2
Input
cbbd
Output
2
Try the problem first. Open one hint at a time.
Let lps[i][j] be the answer for the part of the word from i to j.
Equal end letters add 2 to the inside. Otherwise drop one end and take the better result.
Write your Python code, run it on the examples and submit it to hidden tests.
Solve in the editor