Solution
设 JOI 三个字母的前缀个数分别为 $(a,b,c)$。
若要三个字母个数相同，则有 $(b_i-a_i,c_i-a_i)=(b_j-a_i,c_j-a_i)$ 。
map 统计即可。
code:
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
| #include<bits/stdc++.h>
#define maxn
#define ll long long
#define put() putchar('\n')
using namespace std;
inline void read(int &x){
int f=1;x=0;char c=getchar();
while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
x*=f;
}
int n;
struct node{
int x,y;
node(int a=0,int b=0) {x=a;y=b;}
bool operator <(const node &a) const {
if (x^a.x) return x<a.x;
else return y<a.y;
}
};
map<node,int >mp;
int ans=0;
signed main(void){
int i,sum1=0,sum2=0;string s;
read(n);
cin>>s;
mp[node(0,0)]=1;
for (i=0;i<n;i++) {
if (s[i]=='J') sum1--,sum2--;
else if (s[i]=='O') sum1++;
else if (s[i]=='I') sum2++;
if (!mp[node(sum1,sum2)]) mp[node(sum1,sum2)]=i+2;
else ans=max(ans,i+1-mp[node(sum1,sum2)]+1);
}
printf("%d",ans);
return 0;
}
|