问题描述
解题思路
利用两个指针left
,right
,right
从0开始遍历,如果[left, right]
之外的字符串中,每个字符出现次数都小于或等于n / 4
,说明替换[left, right]
可以构成平衡字符串,此时递增left
,直到移除[left, right]
不能构成平衡字符串。
代码
class Solution {
public:
bool check(unordered_map<char, int> &mp, int m) {
if (mp['Q'] > m || mp['W'] > m || mp['E'] > m || mp['R'] > m)
return true;
else
return false;
}
int balancedString(string s) {
int n = s.size(), partial = n / 4;
int res = n;
unordered_map<char, int> chars;
for (auto &c : s)
chars[c]++;
int flag = 1;
for (auto &pa : chars) { // 检查字符串本身是否平衡
if (pa.second != partial)
flag = 0;
}
if (flag == 1)
return 0;
for (int right = 0, left = 0; right < n; right++) {
chars[s[right]]--;
while (left <= right && !check(chars, partial)) {
chars[s[left]]++;
res = min(right - left + 1, res);
left++;
}
}
return res;
}
};
标签:1234,right,string,int,chars,replace,mp,字符串,left
From: https://www.cnblogs.com/zwyyy456/p/17116885.html