Caitlin snow is extemely upset upon the events of Escape from Earth-2. Zoom took away Jay Garrick from her. Now she wants to seek revenge against Zoom, so she is trying to come up with Velocity-X serum which will increase the speed of Barry Allen aka The Flash. She creates the serum using the components 'X', 'Y' and 'Z'. The serum is composed of a sequence of these components and it's effect on Barry depends upon the the sequence interval, which is defined as the difference between the length of the longest substring with equal number of X's,Y's and Z's and the length of the shortest substring with equal number of X's,Y's and Z's. More the sequence interval, faster he will run. She creates a number of sequences and tries to find the sequence interval for all the sequences. As the number of sequences are large, she plans to come up with an algorithm to find the sequence intervals efficiently and to find the maximum sequence interval out of all the sequences generated. Cisco and Harry are busy in developing a trap for Zoom and Felicity is stuck with team Arrow to find about Genesis, so please assist Cait in finding the sequence interval and do it fast coz ZOOM IS COMING.
The first line of the input consists of the number of sequences 'n' (2 <= n <= 1000).
The next 'n' lines consist of a string 's' (3 <= length <= 10000) describing the sequence. The string will have only the alphabets 'X','Y' and 'Z'.
Output 'n' lines containing the sequence distance(interval) of the correspondng input string 's'.
The 'n+1' th line contains the index (1-based) of the string with the maximum sequence distance. If multiple strings have maximum sequence distance then output the
index of the one that appears first in the input.
Sample Input 3 XYZXYZXYZ XXYYZZXYZ XXXYYYZZZ Sample Output 6 6 0 1
In the given sample case,
for string XYZXYZXYZ (1) Longest = 9 Shortest = 3 Sequence distance = 6
for string XXYYZZXYZ (2) Longest = 9 Shortest = 3 Sequence distance = 6
for string XXXYYYZZZ (3) Longest = 9 Shortest = 9 Sequence distance = 0
(1) and (2) have the maximum value so n+1th line contains 1.
|Time Limit:||5 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, SCM chicken, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.