C++에서 균형 문자열의 하위 문자열 바꾸기

<시간/>

4가지 종류의 문자 'Q', 'W', 'E' 및 'R'만 포함하는 문자열이 있다고 가정합니다. 문자열의 각 문자가 n/4번 나타나면 문자열이 균형을 이룹니다. 여기서 n은 문자열의 길이입니다. 원래 문자열이 균형을 이루도록 동일한 길이의 다른 문자열로 대체될 수 있는 부분 문자열의 최소 길이를 찾으십시오. 따라서 s ="QQWE"이면 출력은 1이 됩니다. 이는 Q를 R로 바꿀 수 있기 때문입니다. 그래서 "RQWE"가 균형을 이룹니다.

문자열이 이미 균형을 이루고 있으면 0을 반환합니다.

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

하나의 지도 만들기
s의 각 문자에 대해 문자의 빈도를 맵에 저장합니다. n :=s의 크기
res :=n, 왼쪽 :=0
0 ~ n – 1 범위의 오른쪽
- m[s[right]] 1 감소
- 남은 동안
- res :=최소 해상도, 오른쪽 – 왼쪽 + 1
- m[s[left]] 1씩 증가
- 왼쪽으로 1 증가

반환 결과

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

예시

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int balancedString(string s) {
      unordered_map <char, int> m;
      for(int i = 0;i<s.size();i++)m[s[i]]++;
      int n = s.size();
      int res = n;
      int left = 0;
      for(int right = 0;right<n;right++){
         m[s[right]]--;
         while(left<n && m['Q']<=n/4 && m['W'] <=n/4 && m['E'] <=n/4 && m['R']<=n/4){
            res = min(res, right - left + 1);
            m[s[left]]+=1;
            left++;
         }
      }
      return res;
   }
};
main(){
   Solution ob;
   cout << (ob.balancedString("QQEQ"));
}

입력

"QQEQ"