C++에서 가장 오래 반복되는 문자 부분 문자열로 바꾸기

<시간/>

문자열 텍스트가 있다고 가정하고 문자열에서 두 문자를 교환할 수 있습니다. 반복되는 문자가 있는 가장 긴 부분 문자열의 길이를 찾아야 합니다. 따라서 입력이 "ababa"와 같으면 결과는 3이 됩니다. 첫 번째 b를 마지막 a로 바꾸거나 마지막 b를 첫 번째 a로 바꾸면 가장 오래 반복되는 문자는 "aaa"가 되므로 길이는 다음과 같습니다. 3.

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

맵 cnt를 정의하고, ret :=1, j :=0, n :=텍스트 크기, v :=0으로 설정하고, x라는 세트를 정의하고, m이라는 또 다른 맵을 생성합니다. m은 각 문자의 빈도를 유지합니다. 텍스트로.
a :=* 및 b :=*
설정
범위 0에서 n까지의 i에 대해
- cnt[text[i]] 1 증가
- x에 텍스트[i] 삽입
- cnt[text[i]]가 2이면
  - *인 경우. 그러면 a :=text[i], 그렇지 않으면 b :=text[i]
- a가 *가 아니고 b도 *가 아니거나 x의 크기가 2보다 큰 경우
  - cnt[text[j]] 1 감소
  - cnt[text[j]]가 1이면
    - text[j]가 a이면 a :=*를 설정하고, 그렇지 않으면 b :=*
- cnt[text[j]]가 0이면 x에서 text[j]를 삭제합니다.
- 더 큼 :=cnt[a]> cnt[b]이면 b
- x의 크기가 1이거나 m[greater] – cnt[greater]가 0이 아닌 경우
  - ret :=ret의 최대값, i – j + 1
- 그렇지 않으면 ret :=ret의 최대값, i – j
반환 반환.

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int maxRepOpt1(string text) {
      int ret = 1;
      map <char, int> cnt;
      int j = 0;
      int n = text.size();
      int v = 0;
      set <char> x;
      map <char, int> m;
      for(int i = 0; i < text.size(); i++)m[text[i]]++;
      char a = '*', b ='*';
      for(int i = 0; i < n; i++){
         cnt[text[i]]++;
         x.insert(text[i]);
         if(cnt[text[i]] == 2){
            if(a == '*'){
               a = text[i];
            }else{
               b = text[i];
            }
         }
         while(a != '*' && b != '*' || x.size() > 2){
            cnt[text[j]]--;
            if(cnt[text[j]] == 1) {
               if(text[j] == a) {
                  a ='*';
               }else{
                  b = '*';
               }
            }
            if(cnt[text[j]] == 0) x.erase(text[j]);
            j++;
         }
         char greater = cnt[a] > cnt[b] ? a : b;
         if(x.size() == 1 || m[greater] - cnt[greater]){
            ret = max(ret, i - j + 1);
         }else{
            ret = max(ret, i - j);
         }
      }
      return ret;
   }
};
main(){
   Solution ob;
   cout << (ob.maxRepOpt1("ababa"));
}

입력

"ababa"

C++에서 가장 오래 반복되는 문자 부분 문자열로 바꾸기

예시

입력

출력