春季赛day14 Identical Letters

题目描述

Streak of identical letters always fascinates computer scientists and, as such, the scientists always look for such consecutive sequence of identical letters. 

Given a string of lowercase letters and an integer m, determine the maximum number of consecutive identical letters in the string if you can remove up to m letters from the string. Note that you do not have to remove exactly m letters. 

输入

The first input line provides the string (1 ≤ string length ≤ 2×105); it starts in column 1 and contains only lowercase letters. The second input line contains an integer, m (0 ≤ m ≤ string length), indicating the maximum number of letters you can remove from the string. 

输出

Print the maximum number of consecutive identical letters in the string if you can remove up to m letters from the string. 

样例输入 Copy

【样例1】
bbazbcbbbcybbx 
2 
【样例2】
bbazbcbbbcybbx 
5
【样例3】
zabcadyhxwuy
5

样例输出 Copy

【样例1】
5
【样例2】
8
【样例3】
2

提示

For the first Sample Input, we can remove the two letters at positions 10 and 11. 
For the second Sample Input, we can remove the letters at positions 3, 4, 6, 10 and 11. 
For the third Sample Input, we can create ”…aa…” or ”…yy…”, each of length 2

一开始是枚举每个字母，把相同长度和中间夹杂的取出部分改写成数字串，然后滑动窗口求最优。

原来直接滑动窗口保证区间C不大于N就可以了

被豆包秒掉了T_T

代码 

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
string s;
int n,un[200009],len;
int find(int x){
	int ans=0,k=0,l=0,r=0,c=0;
	while(r<len){
		if(un[r]!=x)c++;else k++;
		while(l<=r&&c>n){
			if(un[l]!=x)c--;else k--;
			l++;
		}
		ans=k>ans?k:ans;
		r++;
	}
	return ans;
}
int main(){
	cin>>s>>n;
	int ans=0;len=s.length();
	for(int i=0;i<len;++i)un[i]=s[i]-'a';
	for(int i=0;i<26;++i){
		int k=find(i);
		ans=k>ans?k:ans;
	}
	cout<<ans;
	return 0;
}