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

Data Range

对于所有数据, 满足 \(1 \leq n \leq 2 \times 10^5\)

Explanation

记 \(cnt[i][0]\) 为第 \(1-i\) 个字符中 J 出现的次数, 以此类推.

则某一个字符串符合题设的前提条件是:

\[\begin{cases} cnt[j][0] - cnt[i][0] = cnt[j][1] - cnt[i][1] & \\ cnt[j][1] - cnt[i][1] = cnt[j][2] - cnt[i][2] & \end{cases}\]

化简该式可得:

\[\begin{cases} cnt[i][0] - cnt[i][1] = cnt[j][0] - cnt[j][1] & \\ cnt[i][1] - cnt[i][2] = cnt[j][1] - cnt[j][2] & \end{cases}\]

然后用一个 STL 红黑树套一个 pair 瞎搞一发就可以了.

记得预先放进去一个 pair(0, 0) 以防止溢出.

妥妥的结论题......

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <map>

using namespace std;
typedef long long lli;
const int maxn = 200100;

int n, arr[maxn];

int main(int argc, char** argv)
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        char ch = '\0'; while (ch < 'A' || ch > 'Z') ch = getchar();
        arr[i] = ch == 'J' ? 0 : (ch == 'O' ? 1 : 2);
    }
    // Concatencating sums and values
    static int c[3] = { 0, 0, 0 };
    int res = 0;
    map<pair<int, int>, int> mp;
    mp[make_pair(0, 0)] = 0;
    for (int i = 1; i <= n; i++) {
        c[arr[i]] += 1;
        pair<int, int> pr = make_pair(c[0] - c[1], c[1] - c[2]);
        if (mp.find(pr) == mp.end())
            mp[pr] = i;
        else
            res = max(res, i - mp[pr]);
    }
    // Result get!
    printf("%d\n", res);
    return 0;
}