1 second
256 megabytes
standard input
standard output
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?
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.
Print the only integer — the maximum beauty of the string Vasya can achieve by changing no more than k characters.
4 2
abba
4
8 1
aabaabaa
5
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".
题意:给你一串字符串和k个修改字符串的机会,让这个字符串获得最长连续相同子串
题解:所谓尺取法,顾名思义,就是一把尺子(固定某一条件),不断向右(向左)移动,不断更细我们要的答案。在这里,我们只要从左往右,让修改的字符个数从0慢慢增加到k,中途将字符改成同一个字符(a改成b或者b改成a都行),最后修改字符数固定为k,每次向右移动时,如果字符串需要修改,那就改掉右面的字符,将之前最左边的字符换回来。那么我们可以用一个队列去实现。
如果你看不懂上面也没关系,我再讲具体一些。我们从左边开始,扫描字符串。如果遇到a,那就把a丢进队列,如果遇到b,且此时队列中b的个数不超过k的话,就把b丢进去。如果b的个数等于k,且又遇到一个b,那就记录下此时队列长度,这个时候队列里k个b可以当作a,所以可以记录队列元素个数,更新答案最大值。之后将队列前面元素弹出,直到弹出一个b,再将新的b压进队列……一直扫描直到字符串尾。
接下来将a和b互换,重复上面步骤,更新最大值。最后输出最大值。
代码如下
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
char s[];
int main()
{
int n,k;
scanf("%d%d",&n,&k);
scanf("%s",s);
queue <char> Q;
int maxn=;
int len=;
for (int i=; i<n; i++)
{
if (s[i]=='a')
Q.push(s[i]);
else if (len<k)
{
len++;
Q.push(s[i]);
}
else
{
maxn=max(maxn,(int)Q.size());
while (!Q.empty()&&Q.front()=='a')
Q.pop();
if (!Q.empty())
{
Q.pop();
Q.push(s[i]);
}
}
}
maxn=max(maxn,(int)Q.size());
while (!Q.empty()) Q.pop();
len=;
for (int i=; i<n; i++)
{
if (s[i]=='b')
Q.push(s[i]);
else if (len<k)
{
len++;
Q.push(s[i]);
}
else
{
maxn=max(maxn,(int)Q.size());
while (!Q.empty()&&Q.front()=='b')
Q.pop();
if (!Q.empty())
{
Q.pop();
Q.push(s[i]);
}
}
}
maxn=max(maxn,(int)Q.size());
printf("%d\n",maxn);
return ;
}