可转换最长子串

题目描述

有一个仅包含’a’和’b’两种字符的字符串s，长度为n，每次操作可以把一个字符做一次转换（把一个’a’设置为’b’，或者把一个’b’置成’a’)；但是操作的次数有上限m，问在有限的操作数范围内，能够得到最大连续的相同字符的子串的长度是多少。.

输入描述:

第一行两个整数 n , m (1<=m<=n<=50000)，第二行为长度为n且只包含’a’和’b’的字符串s。

输出描述:

输出在操作次数不超过 m 的情况下，能够得到的 最大连续 全’a’子串或全’b’子串的长度。

示例1

输入

8 1
aabaabaa

输出

5

说明

把第一个 'b' 或者第二个 'b' 置成 'a'，可得到长度为 5 的全 'a' 子串。

思路:

用滑动窗口法

代码:

#include<stdio.h>
int main(){
    char c[500001];
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++){
        scanf("%c",&c[i]);
    }
    int r=0,l=0,maxl=0,an=0,bn=0;
    while(r<n){
        if(c[r]=='a') an++;
        else bn++;
        if(an<=m||bn<=m){
            r++;
        }else{
            if(r-l>maxl) maxl = r-l;
            if(c[l]=='a'){
                an--;
                l++;
            }else{
                bn--;
                l++;
            }
            r++;
        }
    }
    if(r-l >maxl) maxl = r-l;
    printf("%d",maxl);
}

代码效率：

运行时间：4ms, 超过61.29%用C提交的代码
占用内存：416KB, 超过83.87%用C提交的代码