题目大概说给一个由a和b组成的字符串,最多能改变其中的k个字符,问通过改变能得到的最长连续且相同的字符串是多长。
用尺取法,改变成a和改变成b分别做一次:双指针i和j,j不停++,然后如果遇到需要改变且改变次数用完就让i++更正改变次数,最后更新答案。时间复杂度O(n)。
另外,注意到k=0的情况。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
char str[];
int main(){
int n,k;
scanf("%d%d%s",&n,&k,str);
int i=,j=,tmpn=,tmpk=,ans=;
while(j<n){
if(str[j]=='a'){
++tmpn;
}else if(k==){
tmpn=;
}else{
while(tmpk==k){
if(str[i]=='b'){
--tmpk;
}
--tmpn;
++i;
}
++tmpk;
++tmpn;
}
ans=max(ans,tmpn);
++j;
}
i=; j=; tmpn=; tmpk=;
while(j<n){
if(str[j]=='b'){
++tmpn;
}else if(k==){
tmpn=;
}else{
while(tmpk==k){
if(str[i]=='a'){
--tmpk;
}
--tmpn;
++i;
}
++tmpk;
++tmpn;
}
ans=max(ans,tmpn);
++j;
}
printf("%d",ans);
return ;
}