1035: 字符串中连续出现最多的字母
题目描述
PIPI又来刁难你胖虎了。
PIPI有一个只包含小写字母的字符串，它想通过交换字符串中字母的位置，使相同的字母出现在一起（如aba，可以交换第一个a和第二个b使其变成baa）
不幸的是PIPI最多只能交换K次（不然就成了一道水题~哈哈哈），每次只能交换两个位置的字母。现在问你通过最多K次交换能够得到的连续出现的相同字母的最大数量！
比如字符串“bababbaa”且K=1，那么通过交换第一个和第四个字母得到“aabbbbaa"，最多连续出现了4个b，所以答案就是4啦~
怎么样~你胖虎又被PIPI难住了吗？
输入
多组数据。
第一行包含一个整数K.(1<=K<=100000)
第二行包含一个只含小写字母的字符串。
对于30%的数据，字符串长度<=100
对于90%的数据，字符串长度<=1000
对于100%的数据，字符串长度<=100000
输出
对于每组数据输出通过最多K次交换能够得到的连续出现的相同字母的最大数量。
样例输入
1
bababbaa
样例输出
4
思路 1
本题要求通过最多 k 次交换所能得到的最大相同字母字符串的长度，直观想法是遍历每一个可能的区间长度（2 ~ len），对于每一个可能的区间长度 mid，依次检查 [0，mid - 1] 、[1，mid] 、…… 、 [len - mid，len - 1] 这些区间中是否有符合条件的区间。
? 若有则更新答案的区间长度，然后检查下一个更大的区间范围
? 若此区间已经没有符合条件的了则可以直接跳出循环。
但此方法时间复杂度为 o（n^2），会超时。因此，使用二分法来枚举区间长度，时间复杂度降到 o（nlogn）。
#include<bits/stdc++.h>
using namespace std;
char str[100010];
int pre[100010][26];// pre[i][j] 表示 str[0] ~ str[i - 1]：有 pre[i][j] 个字母 'a' + j
int main()
{
int k;while(scanf("%d", &k) != EOF){
scanf("\n%s", str);int len = strlen(str);for(int i = 1; i <= len; i++){
for(int j = 0; j < 26; j++){
pre[i][j] = pre[i - 1][j];}pre[i][str[i - 1] - 'a']++;}// 二分找区间int l = 1, r = len, ans = 0;while(l <= r) {
bool flag = false;int mid = (l + (r - l) / 2); //防溢出 for(int i = 0; i + mid <= len; i++) // 枚举每一个长度为 mid 的区间 {
/* 如果区间 [i, i + m - 1] 内含字母 c + 'a' 的个数 + 交换次数 k 大于等于区间长度(大于可能是交换次数多)，且整个字符串含字母 c + 'a' 数目大于等于 mid， 则 [i, i + m - 1] 通过最多 k 次交换可以使得整个区间全部为同一字母 c + 'a' ；其实可以找出区间内出现次数最多的字母，但是区间长度大时远远超出 26，所以不如直接遍历 26 个字母看否有满足该区间长度的字母 */for(int c = 0; c < 26; c++){
if(pre[i + mid][c] - pre[i][c] + k >= mid && pre[len][c] - pre[0][c] >= mid) {
flag = true;break;}}}if(flag) {
ans = mid;l = mid + 1;} elser = mid - 1;}printf("%d\n", ans);}return 0;
}
思路 2
滑动窗口，初始时，l = 0，r = 0，对于区间 [l + 1，r]，
? 1 若满足题目条件（最多交换 k 次使得区间内字母相同）则 ans = max(ans，r - l)，r++（检查更大区间是否满足条件）；
? 2 否则 l–，缩短区间长度（更有可能满足条件）。
#include<bits/stdc++.h>
using namespace std;
char str[100010];
int pre[100010][26];// pre[i][j] 表示 str[0] ~ str[i - 1]：有 pre[i][j] 个字母 'a' + j
int main()
{
int k;while(scanf("%d", &k) != EOF){
scanf("\n%s", str);int len = strlen(str);// pre[i][j] for(int i = 1; i <= len; i++){
for(int j = 0; j < 26; j++){
pre[i][j] = pre[i - 1][j];}pre[i][str[i - 1] - 'a']++;}int ans = 0, l = 0, r = 0, c;for(; r < len; r++) {
bool flag = true;while(flag){
// 检查 26 个字母的理由同思路 1。for(c = 0; c < 26; c++){
//满足条件则停止减小区间长度if(pre[r + 1][c] - pre[l + 1][c] + k >= r - l && pre[len][c] - pre[0][c] >= r - l){
flag = false;break;}}if(flag)l++;}ans = max(ans, r - l);}printf("%d\n", ans);}return 0;
}