JOI Spring Training Camp 2013/14
Original Statement / Submission Site
Mr. JOIOJI is JOI-kun's uncle. He likes his name, which contains exactly two occurrences of each of the letters J, O, and I.
Recently, Mr. JOIOJI had a child. He wants to give his child a name that, like his own, consists only of the letters J, O, and I, with each of the three letters occurring exactly the same number of times.
Mr. JOIOJI possesses a scroll that has been passed down through his family for generations. A poem is written on the scroll. The poem is a string of length N consisting only of the three letters J, O, and I.
Among all contiguous substrings of the poem containing exactly the same number of Js, Os, and Is, Mr. JOIOJI intends to choose the longest one as the name of his child.
Given the poem written on Mr. JOIOJI's scroll, determine the maximum length of a contiguous substring containing exactly the same number of Js, Os, and Is.
The input is given from standard input in the following format:
N S
N, the length of the poem written on the scroll.S of length N, representing the poem. Every character of S is J, O, or I.Print one integer: the maximum length of a contiguous substring of the poem containing exactly the same number of Js, Os, and Is. If no such nonempty substring exists, print 0.
1 ≤ N ≤ 200000S is J, O, or I.N ≤ 200N ≤ 4000There are no additional constraints.
10 JOIIJOJOOI
6
In this sample, the scroll contains the poem JOIIJOJOOI of length 10.
The poem contains the contiguous substring IIJOJO, which has exactly two occurrences of each of J, O, and I. There is no contiguous substring containing at least three occurrences of each letter in equal numbers. Therefore, the answer is the length of IIJOJO, which is 6.
8 IOIIJIIO
0
The poem contains no contiguous substring satisfying the condition, so the output is 0.
20 JJIOOIJIJOIOJIOJOOIJ
15