C. Vasya and String

꿈틀꿈틀, inch worm

출처: CodeforcesC. Vasya and String

파라메트릭 서치로도 풀 수 있다.

[-] Collapse

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<climits>
#include<cmath>
#include<cstring>
using namespace std;

string str;
int ans = 1;
int k, n;
int main(){
    //freopen("input.txt", "r", stdin);
    cin >> n >> k >> str;

    int l, r;
    l = r = 0;
    int tk = k;
    while (r < str.size()){
        if (str[r] == 'b') tk--;
        r++;
        while (tk < 0 && l < r){
            if (str[l] == 'b') tk++;
            l++;
        }
        ans = max(ans, r - l);
    }

    l = r = 0;
    tk = k;
    while (r < str.size()){
        if (str[r] == 'a') tk--;
        r++;
        while (tk < 0 && l < r){
            if (str[l] == 'a') tk++;
            l++;
        }
        ans = max(ans, r - l);
    }

    cout << ans;

    return 0;
}