前言

本来是从树状数组题单来的。

但是看到了这个远古讨论帖，性质就变化了（确信）。

Solution

相信很多人看到这道题的时候和我反应是一样的：

“这……三者出现次数不同的条件是宽泛的，估计答案左右侧应该都是靠近端点的。”

但是又没有一个具体结论。

然后看到了这句话：“最长的子串满足左端点在 $1$ 到 $3$ 或右端点在 $n-2$ 到 $n$。然后暴力。”

豁然开朗，估计结论是正确的，事实上确实也是。羡慕大佬的一眼顶针猜结论能力。

证明一下吧。

Step 1

容易发现，要证明如上结论，只需证明：

“对于一个合法解 $S$，只要左右各有 $3$ 字符，必然有完全包含 $S$ 的更优解。”

因为这样，只要一个解两端点都不在左右 $3$ 个，就必能扩展出更优解。

Step 2

为了严谨，还是分类讨论 $S$ 的组成情况，

由于随便选第一个是长为 $1$ 的解，所以讨论 $S$ 长为 $1$ 无意义，先钦定（？）$length(S)>1$。

如果 $S$ 仅由一种字符构成，即出现次数三元组是 $(x,0,0)$，那么左边加一个，变成 $(x+1,0,0)$ 或者 $(x,1,0)$ 都是满足条件的。

即原解是可以扩展的。

Step 3

如果 $S$ 由多种字符构成，那出现次数必然互不相同，假设其出现次数三元组 $(k+x,k+y,k)$。

设这三个字母为 $D,E,F$。

观察在某一边加一个字母的意义：对三元组中一个值加 $1$。

容易发现，如果没有出现三元组相邻两项差值为 $1$，那我把任意一项加 $1$ 仍然不会有重复数字出现，即此时随便加一个字母仍合法。

所以相邻两项必然有差值为 $1$，再分类讨论。

Case 1:$(k+y+1,k+y,k),y>1$

此时 $S$ 左右两侧字母都只能是 $E$（是按照我上面的加粗假设），否则单选不是 $E$ 那个必会是新的合法解。

即使两边都是 $E$，同时选也会变成 $(k+y+1,k+y+2,k)$ 是合法解。

Case 2:$(k+x,k+1,k),x>2$

此时 $S$ 左右两侧字母都只能是 $F$，否则单选不是 $F$ 那个必会是新的合法解。

即使两边都是 $F$，同时选也会变成 $(k+x,k+1,k+2)$ 是合法解。

Case 3:$(k+2,k+1,k)$

显然左右必然不是 $D$，而且如果左右都是 $E$，同时选后是合法解。

Case 3.1:$()()E|S|F()()$

此时总的出现次数三元组：$(k+2,k+2,k+1)$，左右两边只能都是 $F$。

即为 $()FE|S|FF()$

单选左边两个得到最左边为 $F$，单选右边两个得到最右边为 $E$，

然而对于 $FFE|S|FFE$，简单全选后出现次数为 $(k+2,k+3,k+4)$。是合法的解。

Case 3.2:$()()F|S|F()()$

此时总的出现次数三元组：$(k+2,k+1,k+2)$，左右两边只能都是 $E$。

即为 $()EF|S|FE()$

单选左边两个得到最左边为 $F$，单选右边两个得到最右边为 $F$，

然而对于 $FEF|S|FEF$，简单全选后出现次数为 $(k+2,k+3,k+4)$。是合法的解。

故对于所有情况总是能扩展出合法解。

证明完毕。

代码是简单的，前缀和预处理后枚举即可。

AC 代码

#include<bits/stdc++.h>
using namespace std;
int n,i,j,b[1919810],c[1919810],s[1919810],ans;
void check(int x,int y)
{
	int cb=b[y]-b[x],cc=c[y]-c[x],cs=s[y]-s[x];
	if(cb==0&&cc==0||cs==0&&cb*cc==0)
	ans=max(ans,y-x);
	if(cb!=cc&&cc!=cs&&cs!=cb)
	ans=max(ans,y-x);
}
string a;
int main()
{
	cin>>n>>a;a="6"+a;
	for(i=1;i<=n;i++)
	{
		b[i]=b[i-1];
		c[i]=c[i-1];
		s[i]=s[i-1];
		if(a[i]=='B') b[i]++;
		if(a[i]=='C') c[i]++;
		if(a[i]=='S') s[i]++;
	}
	for(i=0;i<3;i++)
		for(j=i+1;j<=n;j++)
			check(i,j);
	for(i=n-2;i<=n;i++)
		for(j=0;j<i;j++)
			check(j,i);
			cout<<ans;
	return 0;
 } 

The End.