题目描述
小P马上就要来到程序设计大赛的现场、上了，他希望能够AK这次比赛，所以他找到了一个字符串。
这个字符串长度为n，由A和K组成。这个字符串被小p称为AK串。小P任意截取一个区间s，使得这个区间从左往右或从右往左在读取子串的过程中，子串中字母K的个数始终不小于A的个数。小p希望知道能够截取区间s的最大长度。
如果小p得到了这个区间的最大长度，那么他就会得到一个AK 这次比赛的秘籍，请你帮助他得到这个区间的最大长度。
输入
第一行一个整数n (n<=106)，接下来一个长度为n的只含有A,K的字符串
输出
一个整数，区间的最大长度
样例输入 Copy
6
AKAKKA
样例输出 Copy
4
提示
样例解释
取出区间为KAKK 对于30%数据，N<=2000。
对于另外10%数据，a或者k其中一个仅出现一次。
对于全部数据 N<=10^6。
错误代码：
//筛选法？ AK
#include<iostream>
#include<cstring>
using namespace std;
const int maxn=;
string str;
int book[];
int b[];
int main()
{
memset(book,,sizeof(book));
memset(b,,sizeof(b));
int n,x=,y=,j,i,tmp=;
cin>>n;
cin>>str;
str=' '+str;
// cout<<str.length()<<endl;
// for(i=1;i<=n;i++) cout<<book[i]<<" ";
for(i=;i<=n;i++){//y>x
if(str[i]=='A') x++;
else y++;
if(y<x) {
book[i]=;
x=;
y=;}
else {
book[i]=book[i-]+;
// cout<<"i="<<i<<endl;
}
}
x=;
y=;
for(i=n;i>=;i--){//y>x
if(str[i]=='A') x++;
else y++;
if(y<x) {
b[i]=;
x=;
y=;}
else {
b[i]=b[i+]+;
// cout<<"i="<<i<<endl;
}
}
for(i=;i<=n;i++) {
if(book[i]&&b[i]) tmp=max(tmp,max(b[i],book[i]));
}
cout<<tmp<<endl; }
AC代码：
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
cin>>n;
string str;
cin>>str;
int i=,j=;//[i，j]
int a=,k=;
int ans=;
while(){
while(j<str.size()&&k>=a){
if(str[j]=='A')a++;
if(str[j]=='K')k++;
j++;
if(k>=a){
int cnt=;
for(int r=j-;r>=i;r--){
if(str[r]=='A')cnt--;
if(str[r]=='K')cnt++;
if(cnt<)break;
}
if(cnt>=)ans=max(ans,j-i);
}
}
if(k>=a)break;
while(i<j && k<a){
if(str[i]=='A')a--;
if(str[i]=='K')k--;
i++;
}
}
cout<<ans<<endl;
return ;
}
分析：