C++ 中平衡字符串的子字符串替换

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

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

要解决此问题，我们将遵循以下步骤：

  • 创建一个映射 m
  • 对于 s 中的每个字符，将字符的频率存储到映射中，n := s 的大小
  • res := n，left := 0
  • 对于 right 从 0 到 n – 1
    • 将 m[s[right]] 减少 1
    • 当 left < n 且 m[Q] <= n/4 且 m[W] <= n/4 且 m[E] <= n/4 且 m[R] <= n/4 时
      • res := res 和 right – left + 1 的最小值
      • 将 m[s[left]] 增加 1
      • 将 left 增加 1
  • 返回 res

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

示例

 在线演示

#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

更新于: 2020 年 5 月 2 日

377 次查看

启动您的 职业生涯

通过完成课程获得认证

开始学习
广告