题目链接:
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 denotesbeauty 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 题意: 问最多改变k个字母才能使相同字母组成的子串最长; 思路: 最长的那个字串可以是a组成的,也可能是b组成的,现在枚举最长的子串的左端点,二分右端点,找到最长的长度,对于a,b两种情况都这样处理;用尺取法也可以搞; AC代码:
#include <bits/stdc++.h>
/*
#include <iostream>
#include <queue>
#include <cmath>
#include <map>
#include <cstring>
#include <algorithm>
#include <cstdio>
*/
using namespace std;
#define Riep(n) for(int i=1;i<=n;i++)
#define Riop(n) for(int i=0;i<n;i++)
#define Rjep(n) for(int j=1;j<=n;j++)
#define Rjop(n) for(int j=0;j<n;j++)
#define mst(ss,b) memset(ss,b,sizeof(ss));
typedef long long LL;
const LL mod=1e9+;
const double PI=acos(-1.0);
const int inf=0x3f3f3f3f;
const int N=1e5+;
int n,sum[N],k;
char s[N];
int check(int x,int y)
{
if(sum[x]-sum[y]<=k)return ;
return ;
}
int main()
{
scanf("%d%d",&n,&k);
scanf("%s",s);
sum[]=;
for(int i=;i<n;i++)
{
if(s[i]=='a')sum[i+]=sum[i];
else sum[i+]=sum[i]+;
}
int ans=;
for(int i=;i<=n;i++)
{
int l=i,r=n;
while(l<=r)
{
int mid=(l+r)>>;
if(check(mid,i-))l=mid+;
else r=mid-;
}
ans=max(ans,l-i);
}
for(int i=;i<n;i++)
{
if(s[i]=='b')sum[i+]=sum[i];
else sum[i+]=sum[i]+;
}
for(int i=;i<=n;i++)
{
int l=i,r=n;
while(l<=r)
{
int mid=(l+r)>>;
if(check(mid,i-))l=mid+;
else r=mid-;
}
ans=max(ans,l-i);
}
cout<<ans<<"\n";
return ;
}