在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