双端队列 C. Vasya and String
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.
string s;
int main()
{
int n,k;
while(cin>>n>>k){
cin>>s;
int start = 0;
int ans = 0;
deque<int> De;
for(int i = 0;i < s.size();i ++){
if(s[i] == 'b') De.push_back(i);
if(De.size() > k){
start = De.front()+1;
De.pop_front();
}
ans = max(ans,i-start+1);
}
De.clear();
start = 0;
for(int i = 0;i < s.size();i ++){
if(s[i] == 'a') De.push_back(i);
if(De.size() > k){
start = De.front()+1;
De.pop_front();
}
ans = max(ans,i-start+1);
}
cout<<ans<<endl;
}
return 0;
}
最新文章
- Maven运行时异常java.lang.UnsupportedClassVersionError的解决方案
- Reachability判断网络是否连接
- OpenJudge计算概论-计算鞍点
- 主流手持设备GPU性能比较
- 1.4.8 拼凑在一起(putting the pieces together)
- Ubuntu14.04 安装 PHP cURL
- 【转】STL空间配置器
- Android常用代码集合
- U盘安装CentOS6.x报错:Missing ISO 9660 Image
- in window js 未定义和undifined的区别
- php形式的内容被处理
- 安装Laravel框架,利用composer
- Sublime Text 3 插件
- java基础-温故而知新(02)
- 浏览器和服务器 对http请求(post get) url长度限制
- roadhog 知识点
- android 下拉刷新框架PullToRefreshScrollView(com.handmark.pulltorefresh)
- Android开发-- 使用ADT23 的一些问题
- h5前端项目常见问题汇总
- Unity Game Starter Kit for Windows Store and Windows Phone Store games
热门文章
- 交换分区swap
- spring效验
- apue-ubuntu环境搭建
- 【SVN】总结:svn“Previous operation has not finished; run &#39;cleanup&#39; if it was interrupted“
- Nginx 小入门记录 之 Nginx 配置文件解读(二)
- [Agc029E]Wandering TKHS_树形dp_树上差分
- 5个Linux性能命令
- Guava 工具类之Strings 的使用
- Guava 工具类之 Splitter的使用
- MySQL主从同步报错1507