在C ++中将子字符串替换为平衡字符串

假设我们有一个仅包含4种字符“ Q”，“ W”，“ E”和“ R”的字符串。如果字符串的每个字符出现n / 4次，则该字符串将是平衡的，其中n是字符串的长度。查找可以用相同长度的任何其他字符串替换的子字符串的最小长度，以使原始字符串达到平衡。因此，如果s =“ QQWE”，则输出将为1。这是因为我们可以将Q替换为R，从而使“ RQWE”保持平衡。

如果字符串已经平衡，则返回0。

为了解决这个问题，我们将遵循以下步骤-

• 制作一张映射

• 对于s中的每个字符，将字符的频率存储到map中，n：= s的大小

• res：= n，左：= 0

• 在0到n – 1的范围内

• res：=最小res，右–左+ 1

• 将m [s [left]]增加1

• 向左增加1

• 将m [s [right]]减少1

• 而左<n和m [Q] <= n / 4和m [W] <= n / 4和m [E] <= n / 4和m [R] <= n / 4

• 返回资源

让我们看下面的实现以更好地理解-

示例

#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