题意：

有一个长度为n且由a和b组成的字符串，可以删除其中一个子串（可以不删），使得删除后的字符串的“变化”次数小于等于m次且最长。

变化：如果a[i]!=a[i+1]则为一次变化。

输出删除后最长的长度。

思路：

最近好像经常做前缀和+二分的题目？

题目里出现了最长这种词语，所以要往二分答案上想（然而我还是看了题解做的QAQ

所以枚举删除的子串的长度，其他就由前后缀和预处理出来就可以了。

复杂度是nlogn。

代码：

typedef long long ll;
char a[1000010];
int pre[1000010];//前缀的变化次数（到自己为止）
int suf[1000010];//后缀的变化次数（到自己为止）
int n,m;
void init()
{
    pre[0]=0;
    for(int i=1;i<n;i++)
    {
        if(a[i]!=a[i-1])pre[i]=pre[i-1]+1;
        else pre[i]=pre[i-1];
    }
    suf[0]=0;
    for(int i=n-2;i>=0;i--)
    {
        if(a[i]!=a[i+1])suf[i]=suf[i+1]+1;
        else suf[i]=suf[i+1];
    }
    /*for(int i=0;i<n;i++)
        printf("%d ",pre[i]);
    printf("\n");
    for(int i=0;i<n;i++)
        printf("%d ",suf[i]);
    printf("\n");*/
}
bool judge(int x)
{
    for(int i=0;i<=n-x;i++)
    {
        int temp=0;
        if(i-1>=0)temp+=pre[i-1];
        if(i+x<n)temp+=suf[i+x];
        if(i-1>=0&&i+x<n&&a[i-1]!=a[i+x])temp++;
        if(temp<=m)return true;
    }
    return false;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        scanf("%s",a);
        init();
        if(pre[n-1]<=m){printf("%d\n",n);continue;}
        int l=1,r=n,ans=0;
        while(l<=r)
        {
            int mid=(l+r)>>1;
            if(judge(mid)){ans=mid;r=mid-1;}
            else l=mid+1;
        }
        //printf("%d\n",ans);
        printf("%d\n",n-ans);
    }
    return 0;
}