2016 CodeCraft IIIT Hyderabad Replay |
---|
Finished |
iChandu is a playful young man. He like strings a lot and has an interesting problem for you. He gives a string of lowercase letters of length N. You have to replace exactly one position in the string by character , such that the number of distinct palindromic substrings in the new string is maximized. You also have to find the number of different such strings possible.
First line contains T(1 ≤ T ≤ 5), the number of test cases. Each test case consist of one line, the string iChandu gave you. Length of the string is N(1 ≤ N ≤ 105).
For each test case output two values: maximum number of distinct palindromic substrings in the new string and different number of such strings possible.
1
aba
3 3
Sample test case 1:
Three different strings possible:
distinct palindromic substrings = 3 .
distinct palindromic substrings = 3 .
distinct palindromic substrings = 3 .
Hence maximum distinct palindromic substrings are 3, and count of distinct strings that generate 3 different substrings is 3.
Name |
---|