最大连续的相同字符

题目描述

有一个仅包含’B’和’T’两种字符的字符串s，每次操作可以把一个字符做一次转换（把一个’B’设置为’T’，或者把一个’T’置成’B’)；但是操作的次数有上限k，问在有限的操作数范围内，能够得到最大连续的相同字符的子串的长度是多少。

输入描述

字符串和可以改变的次数
BTTT 1

输出描述

输出在操作次数不超过 k 的情况下，能够得到的 最大连续 全’B’子串或全’T’子串的长度。

算法分析

以B替换T为例，记录每一个B的位置，那么将连续k个B的置换为T必然存在最长的字串。
对索引为i的B而言，将前面k个B置换为A，此时索引为i的B与索引为i-k-1的B之间的字串的长度为
loc[i] - loc[i-k-1]-1。
初始化时，i从k+1开始，因为前面不足k个B的时候，只要全部置为T即可。

示例1

输入：
BTTT 1
输出：
4 (把第一个B变成T)

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
 
using namespace std;
 
string str;
int k;
int n = str.size();
int change_alpha(char a)
{
    vector<int> loc;
    for (int i = 0; i < n; ++i)
        if (str[i] == a) 
            loc.push_back(i);
        loc.push_back(n);
        int max_length = loc[k];
    
    for (int i = k + 1; i < loc.size(); ++i) {
        // loc[i]当前a实际索引, loc[i-k-1] i的前面m个数翻转之后，再前面的未翻转a的索引
        // loc[i] - loc[i-k-1] - 1 之间翻转k个a之后，中间字符的长度。
        max_length = max(max_length, loc[i] - loc[i-k-1] - 1);
    }
    return max_length;
}
 
int main()
{
    cin >> k;
    cin >> str;
    
    cout << max(change_alpha('B'), change_alpha('T')) << endl;
    return 0;
}

参考：https://blog.csdn.net/ansizhong9191/article/details/88365647?utm_medium=distribute.wap_relevant.none-task-blog-title-7