题意简述

给定一个仅含 JOI 的字符串，求最长的子串，满足其中 JOI 出现的次数相等。

题目分析

考虑求出 JOI 出现次数的前缀和，设 $a_i,b_i,c_i$ 分别为 JOI 出现次数的前缀和。考虑什么时候 $s[i,j]$ 中 JOI 出现的次数相等。发现当且仅当 $a_j-a_{i-1}=b_j-b_{i-1}=c_j-c_{i-1}$ 时 JOI 出现的次数相等。可是这样还是不好做。发现可以移项得 $\begin{cases}b_j-a_j=b_{i-1}-a_{i-1}\\c_j-a_j=c_{i-1}-a_{i-1}\end{cases}$，于是可以开个桶 $dp_{i,j}$ 表示当 $\begin{cases}b_k-a_k=i\\c_k-a_k=j\end{cases}$ 时 $k$ 的最小值，于是以 $k$ 结尾的合法子串的最大长度即为 $k-dp_{b_k-a_k,c_k-a_k}$。由于需要的桶数很多，所以可以用 unordered_map 存储，时间复杂度 $O(n)$。

代码

#include<bits/stdc++.h>
using namespace std;
int n,m,i,x=200000,y=200000;
char s[200005];
unordered_map<int,int>dp[400005];
int main(){
	cin.tie(0)->sync_with_stdio(0);
	cin>>n>>s;
	dp[x][y]=-1;
	for(i=0;i<n;i++){
		x+=(s[i]=='O')-(s[i]=='J');
		y+=(s[i]=='I')-(s[i]=='J');
		if(dp[x].count(y))m=max(m,i-dp[x][y]);
		else dp[x][y]=i;
	}
	cout<<m;
}