Atcoder.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”三个字母的连续子串。

输入

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

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

N<=200000

输出

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

样例输入

10

JOIIJOJOOI

样例输出

6

同样,2*10^5数据范围 N * N肯定也不可行,考虑别的办法。

思路参考引自:https://fighting-naruto.blog.luogu.org/solution-at1224

如果用1,2,3分别代表 J,O,I ,用 si[j] 表示 前 j 个位置有多少个 i ,那么区间[i,j]满足条件有:

s1[j] - s1[i-1] = s2[j] - s2[i-1] = s3[j] - s3[i-1]

移项化简

设s2[i] - s1[i] = x[i] , s3[i] - s1[i] = y[i],则只要满足x[j]=x[i-1]并且y[j] = y[i-1]就说明区间[i,j]满足条件

最后只需要找x,y相同的最大的区间[i,j]即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include<cstdio>
#include<iostream>
#include<algorithm>
const int N = 200005;
typedef long long ll;
using namespace std;
ll ans=0;
struct node{
int x,y,id;
}a[N];
char ch;
bool cmp(node a,node b){
return a.x<b.x || (a.x==b.x&&a.y<b.y)|| (a.x==b.x&&a.y==b.y&&a.id<b.id);
}
ll maxx(ll xx,ll yy){
if(xx>yy){
return xx;
}return yy;
}
int main(){
int n;
cin>>n;//x[i]=s2[i]-s1[i] y[i]=s3[i]-s1[i]
for(int i=1;i<=n;i++){
cin>>ch;
a[i].id=i;
if(ch=='J'){
a[i].x=a[i-1].x-1;
a[i].y=a[i-1].y-1;
}if(ch=='O'){
a[i].x=a[i-1].x+1;
a[i].y=a[i-1].y;
}if(ch=='I'){
a[i].x=a[i-1].x;
a[i].y=a[i-1].y+1;
}

}

sort(a,a+n+1,cmp);


int t=a[0].id;
for(ll i=1;i<=n;i++){
if(a[i].x==a[i-1].x && a[i].y==a[i-1].y) ans=maxx(ans,a[i].id-t);
else t=a[i].id;
}

cout<<ans<<endl;
return 0;
}