A garland of n lanterns is strung in a fixed line, each lantern lit in one of the lowercase colors 'a' to 'z', given as a string s of length n read left to right. You want to select two separate groups of lanterns, using every lantern in at most one of the two groups (a lantern may also be left in neither group). Reading each group's lanterns in their original left-to-right order must produce a color sequence that is a palindrome — it reads the same forwards and backwards (a group with no lanterns at all counts as a palindrome of length 0). Among every way of splitting the lanterns into two disjoint palindromic groups, find the maximum possible product of the two groups' sizes, that is, the number of lanterns in the first group multiplied by the number of lanterns in the second group.
A single integer: the maximum product of the sizes of two disjoint palindromic groups chosen from the lanterns.
Example 1
Input
6 abccba
Expected
9
Explanation
s = "abccba" has 6 lanterns at positions 0..5 with colors a,b,c,c,b,a. Taking positions {0,2,5} gives the sequence "a","c","a" = "aca", a palindrome of length 3; the remaining positions {1,3,4} give "b","c","b" = "bcb", also a palindrome of length 3. These two groups are disjoint and use every lantern, giving product 3 * 3 = 9. No split can do better, since the two group sizes can sum to at most 6 and 3 * 3 = 9 is the largest product two non-negative integers summing to at most 6 can reach, so the answer is 9.
Example 2
Input
2 ab
Expected
1
Explanation
s = "ab" is not itself a palindrome (the two colors differ), so the only palindromic groups available are single lanterns or the empty group. Taking {0} = "a" (length 1) and {1} = "b" (length 1) as the two disjoint groups gives product 1 * 1 = 1, which is the best possible, so the answer is 1.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →