#P4236. JOIOJI

    ID: 3453 传统题 1000ms 256MiB 尝试: 1886 已通过: 652 难度: 4 上传者: 标签>CF1500普及+/提高-一维前缀和哈希表状态编码JOI2013~2014春季training合宿

JOIOJI

题目描述

JOIOJI桑是JOI君的叔叔。“JOIOJI”这个名字是由“J、O、I”三个字母各两个构成的。

最近,JOIOJI桑有了一个孩子。JOIOJI桑想让自己孩子的名字和自己一样由“J、O、I”三个字母构成,并且想让“J、O、I”三个字母的出现次数恰好相同 。

JOIOJI桑家有一份祖传的卷轴,上面写着一首长诗,长度为N,由“J、O、I”三个字母组成。JOIOJIさん想用诗中最长的满足要求的连续子串作为孩子的名字。

现在JOIOJI桑将这首长诗交给了你,请你求出诗中最长的、包含同样数目的“J、O、I”三个字母的连续子串。

输入格式

第一行一个正整数 NN,代表这首长诗的长度

接下来一行一个长度为 NN 的字符串S,表示这首长诗,保证每个字符都是“J、O、I”三个字母中的一个

N≤200000N \le 200000

输出格式

输出一行一个正整数,代表最长的包含等数量“J、O、I”三个字母的最长连续子串的长度。如果不存在这样的子串,输出0。

10
JOIIJOJOOI
6