# Bzoj4384 [poi2015]trzy wieże

## 结论题

Posted by yjjr's blog on October 17, 2018 3 minutes to read

# 题目

## Sample Input

9
CBBSSBCSC


## Sample Output

6


# 分析

• 所求答案的最长子串$[l,r]$，3种字母个数最多相差1
• 对于子段$[l,r]$，当$l\in [1,3]\ ,r\in [n-2,n]$时，一定能找到最优解

# code

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
using namespace std;
inline ll read(){
ll f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
//**********head by yjjr**********
const int maxn=1e6+6;
int a[maxn],b[maxn],c[maxn],n,ans=0;
char st[maxn<<1];
int main()
{
n=read();scanf("%s",st+1);
rep(i,1,n)a[i]=a[i-1]+(st[i]=='B'),b[i]=b[i-1]+(st[i]=='C'),c[i]=c[i-1]+(st[i]=='S');
rep(i,1,3)
for(int j=n;j-i+1>ans;j--){
int ta=a[j]-a[i-1],tb=b[j]-b[i-1],tc=c[j]-c[i-1];
if((ta!=tb&&ta!=tc&&tc!=tb)||(!ta)+(!tb)+(!tc)==2){ans=j-i+1;break;}
}
rep(j,n-2,n)
for(int i=1;j-i+1>ans;i++){
int ta=a[j]-a[i-1],tb=b[j]-b[i-1],tc=c[j]-c[i-1];
if((ta!=tb&&ta!=tc&&tc!=tb)||(!ta)+(!tb)+(!tc)==2){ans=j-i+1;break;}
}
cout<<ans<<endl;
return 0;
}