第一行两个整数 n , m (1<=m<=n<=50000),第二行为长度为n且只包含’a’和’b’的字符串s。
输出在操作次数不超过 m 的情况下,能够得到的 最大连续 全’a’子串或全’b’子串的长度。
8 1 aabaabaa
5
把第一个 'b' 或者第二个 'b' 置成 'a',可得到长度为 5 的全 'a' 子串。
def solve(n, m, s): length = m # 长度至少可以达到操作数的上限 cnt_a = s[:m].count('a') cnt_b = m - cnt_a start = 0 # 最大连续的相同字符的子串的起始索引 for i in range(m, n): if s[i] == 'a': cnt_a += 1 # 更新a的个数 else: cnt_b += 1 # 更新b的个数 if min(cnt_a, cnt_b) <= m: # 说明从对子串s[:i+1]进行不超过m个操作就可以使字符串变成一种 # 如果a的数目少,就在m个操作内将a全部变为b,如果b的数目少则将b全部变为a length = max(length , i - start + 1) # 更新长度 elif s[start] == 'a': # 当a和b的长度都超过m时,起点必须要向右移动才能使m个操作内的替代成立 cnt_a -= 1 # 如果起点位置为a,则更新a的个数 start += 1 # 更新起点位置 else: cnt_b -= 1 # 如果起点位置为b,则更新b的个数 start += 1 # 更新起点位置 return length if __name__ == "__main__": n, m = map(int, input().strip().split()) s = input().strip() print(solve(n, m, s))
#include<iostream> #include<vector> #include<algorithm> #include<string> using namespace std; string str; int n, m; int change_alpha(char k) { vector<int> loc; for (int i = 0; i < n; ++i) if (str[i] == k) loc.push_back(i); loc.push_back(n); int max_length = loc[m]; //从头变a/b的初始长度 for (int i = m + 1; i < loc.size(); ++i) { // loc[i]当前k实际索引, loc[i-m-1] i的前面m个数翻转之后,再前面的未翻转k的索引 // loc[i] - loc[i-m-1] - 1 之间翻转m个k之后,中间字符的长度。 max_length = max(max_length, loc[i] - loc[i - m - 1] - 1); } return max_length; } int main() { cin >> n >> m; cin >> str; cout << max(change_alpha('a'), change_alpha('b')) << endl; }