题解 | #编程题2#

贪心算法，按照题目的描述 增加一个修正策略 然后滑动

#include <iostream>
// 滑动窗口 贪心
using namespace std;

int getMax(string &s, int m, char target) {
    int left = 0, right = 0;
    int result = 0, index = 0;
    int n = s.size();

    while (right < n) {
        if (s[right] == target) {
            right++;
        } else {
            index++;
            right++;
            // 这里因为用了一次修正所以 right往后移动一次
            while (index > m) {
                // 超过修正次数了
                if(s[left] != target) {
                    index--;
                }
                left++;
            }
        }
        
        result = max(result, right - left);            
    }
    
    return result;
}

int main() {
    int n, m;
    string str;
    cin >> n >> m;
    cin >> str;
    
    if (m >= n) {
        cout << n << endl;
    } else {
        cout << max(getMax(str, m, 'a'), getMax(str, m, 'b')) << endl;
    }
    
    return 0;
}