codeforce - Vasya and String

标签：尺取，贪心

题目大意
给定一个长度为n（1<=n<=100000）且只包含a和b的字符串和一个数字k（0<=k<=n），最多能更改k个字符，问能得到最长的只包含一种字符的子串长度是多少

思路

首先思考怎样修改能得到最大的长度，从贪心的角度思考，因为最终要求的字符串只包含一种字符，假定为a，那么显然将这k次修改全部用到b上最佳，另一种情况同理，最后在这两种情况中取最大值即可
具体修改过程要用到尺取法，以修改a为例，每次移动右指针，当找到a时，让t++，当t>k时，说明修改次数用完了，这时移动左指针，每找到一个a，让t–，直到t恰好等于k，这时更新一下答案

代码实现

#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
int n, k; 
string s;
int main(){
    cin >> n >> k;
    cin >> s;
    int l = 0, t = 0;
    int ans = 0;
    for(int i = 0; i < n; i++){
    	if(s[i] == 'a') t++;
    	while(t > k){
    		if(s[l] == 'a') t--;
    		l++;
		}
		ans = max(ans, i - l + 1);
	}
	l = 0, t = 0;
	for(int i = 0; i < n; i++){
    	if(s[i] == 'b') t++;
    	while(t > k){
    		if(s[l] == 'b') t--;
    		l++;
		}
		ans = max(ans, i - l + 1);
	}
	cout << ans;
	return 0;
}