在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