View problem - JOIOJI (JOI14_joioji)

Time limit Memory limit # of submissions # of accepted Ratio
1000 ms 256 MiB 112 57 50.89%

JOIOJI-san is JOI-san's uncle. The name "JOIOJI" is made of the characters-"J", "O", "I". Recently, JOIOJI-san has a new child. JOIOJI-san wants his child's name to consist of only of the characters "J", "O", "I" and also wants the name to have an equal number of "J", "O" and "I".

JOIOJI-san's house has an ancestral scroll. On the scroll, there is a poem of $N$ characters where each character is either "J", "O" or "I".

JOIOJI-san wants to name his child with the longest subsequence of the poem that satisfies the condition mentioned above.

(Translator note: ojisan is an honorific in Japanese to refer to one's uncle)

Task

JOIOJI-san gives you the poem that is written on the scroll. Help him find the longest substring that contains an equal number of "J", "O" and "I".

Input Format

Input will be given from the standard input.

  • The first line will contain one integer, $N$, which is the number of characters the poem has.
  • The following line will contain a string $S$ of length $N$, which represents the poem. It is guaranteed that $S$ will only contain the characters "J", "O" and "I" only.

Output Format

Print output to the standard output.

Print a single integer, the maximum length of the longest subsequence of the poem that contains an equal number of "J", "O" and "I". If there are no substrings that fit the criteria for naming JOIOJI-san's child, print $0$.

Constraints

For all test cases, the input will satisfy the following conditions.

  • $1 \le N \le 200,000$

Subtasks

Subtask 1 [5 Marks]

  • $N \le 200$

Subtask 2 [15 Marks]

  • $N \le 4,000$

Subtask 3 [80 Marks]

  • $N \le 200,000$

Sample Testcases

Sample Input Sample Output
10
JOIIJOJOOI
6
8
IOIIJIIO
0
20
JJIOOIJIJOIOJIOJOOIJ
15