C++でバランスの取れた文字列の部分文字列を置き換えます

「Q」、「W」、「E」、「R」の4種類の文字のみを含む文字列があるとします。文字列のそれぞれがn/4回出現する場合、文字列のバランスがとられます。ここで、nは文字列の長さです。元の文字列のバランスをとるために、同じ長さの他の文字列に置き換えることができる部分文字列の最小の長さを見つけます。したがって、s =“ QQWE”の場合、出力は1になります。これは、QをRに置き換えて、「RQWE」のバランスをとることができるためです。

文字列のバランスがすでに取れている場合は0を返します。

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

• 1つのマップを作成するm
• sの各文字について、文字の頻度をマップに保存します。n：=sのサイズ
• res：=n、left：=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"

出力

2