C ++中最长的重复字符替换
假设我们给出了一个仅包含大写字母的字符串s，那么我们最多可以对该字符串执行k次操作。在一个操作中，我们可以选择字符串的任何字符并将其更改为任何其他大写字母。我们必须找到最长的子字符串的长度，该子字符串包含执行上述操作后可以获得的所有重复字母。因此，如果输入类似：“ABAB”且k=2，则输出将为4。这是因为两个“A”与两个“B”，反之亦然。
为了解决这个问题，我们将遵循以下步骤-
maxCount：=0，ans：=0和n：=字符串s的大小
制作一个大小为26的数组cnt，并且j：=0
对于我：=0至n–1
减少cnt[s[j]–'A']
将j增加1
将cnt[s[i]–'A']增加1
maxCount：=maxCount的最大值，count[s[i]–'A']
当j<=i和i–j+1–maxCount>k时，
ans：=ans的最大值，i–j+1
返回ans
例子（C++）
让我们看下面的实现以更好地理解-
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int characterReplacement(string s, int k) {
int maxCount = 0;
int ans = 0;
int n = s.size();
vector <int> cnt(26);
int j = 0;
for(int i = 0; i < n; i++){
cnt[s[i] - 'A']++;
maxCount = max(maxCount, cnt[s[i] - 'A']);
while(j <= i && i - j + 1 - maxCount > k){
--cnt[s[j] - 'A'];
j++;
}
ans = max(ans, i - j + 1);
}
return ans;
}
};
main(){
Solution ob;
cout << ob.characterReplacement("ABAB", 2);
}输入值
"ABAB" 2
输出结果
4