High school student Vasya got a string of length n as a birthday present. This string consists of letters ‘a’ and ‘b’ only. Vasya denotes beauty of the string as the maximum length of a substring (consecutive subsequence) consisting of equal letters.
Vasya can change no more than k characters of the original string. What is the maximum beauty of the string he can achieve?
Input
The first line of the input contains two integers n and k (1 ≤ n ≤ 100 000, 0 ≤ k ≤ n) — the length of the string and the maximum number of characters to change.
The second line contains the string, consisting of letters ‘a’ and ‘b’ only.
Output
Print the only integer — the maximum beauty of the string Vasya can achieve by changing no more than k characters.
Example
Input
4 2
abba
Output
4
Input
8 1
aabaabaa
Output
5
Note
In the first sample, Vasya can obtain both strings “aaaa” and “bbbb”.
In the second sample, the optimal answer is obtained with the string “aaaaabaa” or with the string “aabaaaaa”.
**
题意：求长为n且只含a，b的字符串里，只含k个a或b的字符串的最大长度。
做法：尺取的适用条件一般是连续区间，
分别只考虑含k个a和含k个b的情况，拿含k个b来说明，便利一遍数组，遇到b更新当前选中的区间b的个数，当超出k个时把左端点放到第一个b的下一位，更新最大值。。。最后取两个最大值中的最大值即可。**
using namespace std;char str[maxn];int n,k;int apos[maxn];int bpos[maxn];int main(){ while(scanf("%d%d",&n,&k)==2) { scanf("%s",&str); int a=0,b=0; int an=0,bn=0; int st=0; int end=0; int fbp=0; int bans=-1; for(int i=0;i<n;i++) { if(str[i]=='b') { bpos[bn]=i; b++; bn++; if(b==k+1) { st=bpos[fbp]+1; fbp++; b--; } end++; } else end++; bans=max(bans,end-st); //printf("%d %d %d %d\n",st,end,b,bans); } int aans=-1; st=end=0; int fap=0; for(int i=0;i<n;i++) { if(str[i]=='a') { apos[an]=i; a++; an++; if(a==k+1) { st=apos[fap]+1; fap++; a--; } end++; } else end++; aans=max(aans,end-st); //printf("%d %d %d %d\n",st,end,a,aans); } printf("%d\n",max(aans,bans)); } return 0;}
