C++での最長の繰り返し文字置換

大文字のみで構成される文字列sを指定したとすると、その文字列に対して最大k個の操作を実行できます。 1つの操作で、文字列の任意の文字を選択し、それを他の大文字に変更できます。上記の操作を実行した後に取得できるすべての繰り返し文字を含む最長のサブ文字列の長さを見つける必要があります。したがって、入力が「ABAB」でk =2の場合、出力は4になります。これは、2つの「A」と2つの「B」またはその逆であるためです。

これを解決するには、次の手順に従います-

• maxCount：=0、ans：=0およびn：=文字列のサイズs
• サイズ26の配列cntを作成し、j：=0
• for i：=0からn– 1
  • cnt [s [i] –‘A’]を1増やします
  • maxCount：=maxCountの最大値、count [s [i] –‘A’]
  • j <=iおよびi– j + 1 – maxCount> kの場合、do
    • cnt [s [j] –‘A’]
    を減らします
    • jを1増やします
  • ans：=ansの最大値、i – j + 1
• 回答を返す

例（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