在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

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

    回到顶部