Loading...
Loading...
Loading...
Meera is making a name board for the college fest from letter tiles fixed in a row. She may remove any tiles she likes, but she cannot move the rest. The tiles left behind must read the same from left to right and from right to left.
Given the row of tiles as a string of lowercase letters, print the largest number of tiles she can keep.
Example 1
Input
character
Output
5
Keep c, a, r, a, c to get carac, which reads the same both ways.
Example 2
Input
malayalam
Output
9
The whole row already reads the same both ways.
Try the problem first. Open one hint at a time.
Look at the first and the last tile of a stretch. If they are equal, both can stay as the outer pair.
If they differ, at least one of them must go. Try removing the first, then the last, and keep the better result.
Let best[i][j] be the answer for the tiles from i to j. A single tile gives 1.
Each cell needs shorter stretches inside it. Fill i from the end of the string down to 0, and j from i + 1 up to the end.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor