Krydom: 暁の水平线に胜利を刻むのです

ソロモンの悪夢、見せてあげる!

@krydom12月前

07/13
08:57
STL

[bzoj 4236] JOIOJI

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

JOIOJI桑是JOI君的叔叔。“JOIOJI”这个名字是由“J、O、I”三个字母各两个构成的。
最近,JOIOJI桑有了一个孩子。JOIOJI桑想让自己孩子的名字和自己一样由“J、O、I”三个字母构成,并且想让“J、O、I”三个字母的出现次数恰好相同。
JOIOJI桑家有一份祖传的卷轴,上面写着一首长诗,长度为N,由“J、O、I”三个字母组成。JOIOJIさん想用诗中最长的满足要求的连续子串作为孩子的名字。
现在JOIOJI桑将这首长诗交给了你,请你求出诗中最长的、包含同样数目的“J、O、I”三个字母的连续子串。

♦♦♦♦♦♦   Input   ♦♦♦♦♦♦

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

♦♦♦♦♦♦   Output   ♦♦♦♦♦♦

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

♦♦♦♦♦♦   Sample Input   ♦♦♦♦♦♦

10
JOIIJOJOOI

♦♦♦♦♦♦   Sample Output   ♦♦♦♦♦♦

6

♦♦♦♦♦♦   Hint   ♦♦♦♦♦♦

选择“IIJOJO”这个子串,长度为6,包含“J、O、I”三个字母各2个,这是最长的满足要求的子串。

1<=N<=2*10^5

♦♦♦♦♦♦   题解  ♦♦♦♦♦♦

用f[0..2][1..n]维护前n位中J O I的个数,然后把(f[0][i]-f[1][i],f[1][i]-f[2][i])和它最早出现的时间扔进map里面去,对于每个位置查一下就好

 

[bzoj 4236] JOIOJI