C++에서 가장 오래 반복되는 문자 교체

대문자로만 구성된 문자열 s를 제공했다고 가정하면 해당 문자열에 대해 최대 k개의 연산을 수행할 수 있습니다. 한 번의 작업으로 문자열의 모든 문자를 선택하고 다른 대문자로 변경할 수 있습니다. 위의 작업을 수행한 후 얻을 수 있는 모든 반복 문자를 포함하는 가장 긴 부분 문자열의 길이를 찾아야 합니다. 따라서 입력이 "ABAB" 및 k =2와 같으면 출력은 4가 됩니다. 이는 2개의 'A'와 2개의 'B' 또는 그 반대이기 때문입니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

maxCount :=0, ans :=0 및 n :=문자열 s의 크기
크기가 26이고 j :=0인 배열 cnt를 만듭니다.
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 :=as의 최대값, 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