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

  • Z时代
  • 2024-01-10
  • 分类：综合

假设我们有一个仅包含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

    以上是 在C ++中将子字符串替换为平衡字符串 的全部内容， 来源链接： utcz.com/z/327326.html

    回到顶部