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