1234. Replace the Substring for Balanced String

You are given a string containing only 4 kinds of characters `'Q',` `'W', 'E'` and `'R'`.

A string is said to be balancedif each of its characters appears `n/4` times where `n` is the length of the string.

Return the minimum length of the substring that can be replaced with any other string of the same length to make the original string `s` balanced.

Return 0 if the string is already balanced.

Example 1:

``````Input: s = "QWER"
Output: 0
``````

Example 2:

``````Input: s = "QQWE"
Output: 1
Explanation: We need to replace a 'Q' to 'R', so that "RQWE" (or "QRWE") is balanced.
``````

Example 3:

``````Input: s = "QQQW"
Output: 2
Explanation: We can replace the first "QQ" to "ER".
``````

Example 4:

``````Input: s = "QQQQ"
Output: 3
Explanation: We can replace the last 3 'Q' to make s = "QWER".
``````

Constraints:

• `1 <= s.length <= 10^5`
• `s.length` is a multiple of `4`
• `s `contains only `'Q'``'W'``'E'` and `'R'`.

``````class Solution {
public:
int balancedString(string s) {
int n = s.size(), res = n, left = 0, k = n / 4;
unordered_map<char, int> m;
for (char c : s) ++m[c];
for (int i = 0; i < n; ++i) {
--m[s[i]];
while (left < n && m['Q'] <= k && m['W'] <= k && m['E'] <= k && m['R'] <= k) {
res = min(res, i - left + 1);
++m[s[left++]];
}
}
return res;
}
};
``````

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1234

https://leetcode.com/problems/replace-the-substring-for-balanced-string/

https://leetcode.com/problems/replace-the-substring-for-balanced-string/discuss/408978/JavaC%2B%2BPython-Sliding-Window

LeetCode All in One 题目讲解汇总(持续更新中…)

|

Venmo 打赏

—|—

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation