Loading...
Loading...
Loading...
Karthik is building a word puzzle for his college coding club. The puzzle shows a long random string of lowercase letters. A player scores by finding the longest consecutive piece that reads the same from left to right and from right to left, like level or abba.
Print the length of the longest such piece and the piece itself. If several pieces have the same longest length, print the one that starts leftmost.
Example 1
Input
bananaxyz
Output
5 anana
anana (positions 2 to 6) reads the same both ways. No longer piece does.
Example 2
Input
abacdc
Output
3 aba
aba and cdc both have 3 letters. aba starts further left, so it is printed.
Try the problem first. Open one hint at a time.
Every palindrome has a centre: one letter for an odd length, or the gap between two letters for an even length.
Growing a palindrome outwards from each of the 2n − 1 centres works, but takes about n^2 / 2 steps on aaaa…a, too slow for 10^5 letters.
Inside a long palindrome, the left half mirrors the right half. A centre on the right can start from the radius of its mirror centre on the left, capped at the palindrome's right edge.
Keep the palindrome that reaches furthest right. Grow only beyond that edge, and compare by length first, then by start position, to get the leftmost answer.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor