1234 Replace the Substring for Balanced String 替换子串得到平衡字符串
Description:
You are given a string s of length n containing only four kinds of characters: 'Q', 'W', 'E', and 'R'.
A string is said to be balanced if 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 s balanced. If s is already balanced, return 0.
Example:
Example 1:
Input: s = "QWER"
Output: 0
Explanation: s is already balanced.
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".
Constraints:
n == s.length
4 <= n <= 10^5
n is a multiple of 4.
s contains only 'Q', 'W', 'E', and 'R'.
题目描述：
有一个只含有 'Q', 'W', 'E', 'R' 四种字符，且长度为 n 的字符串。
假如在该字符串中，这四个字符都恰好出现 n/4 次，那么它就是一个「平衡字符串」。
给你一个这样的字符串 s，请通过「替换一个子串」的方式，使原字符串 s 变成一个「平衡字符串」。
你可以用和「待替换子串」长度相同的 任何 其他字符串来完成替换。
请返回待替换子串的最小可能长度。
如果原字符串自身就是一个平衡字符串，则返回 0。
示例：
示例 1：
输入：s = "QWER"
输出：0
解释：s 已经是平衡的了。
示例 2：
输入：s = "QQWE"
输出：1
解释：我们需要把一个 'Q' 替换成 'R'，这样得到的 "RQWE" (或 "QRWE") 是平衡的。
示例 3：
输入：s = "QQQW"
输出：2
解释：我们可以把前面的 "QQ" 替换成 "ER"。
示例 4：
输入：s = "QQQQ"
输出：3
解释：我们可以替换后 3 个 'Q'，使 s = "QWER"。
提示：
1 <= s.length <= 10^5
s.length 是 4 的倍数
s 中只含有 'Q', 'W', 'E', 'R' 四种字符
思路：
滑动窗口
先统计所有字符(QWER)的出现次数, 如果出现次数刚好都是字符串长度的 1/4, 说明不需要替换直接返回 0
然后使用滑动窗口, 窗口中的值要保证所有字符出现次数能够用来替换
也就是说减去滑动窗口中字符的出现次数, 剩下的字符出现次数需要都小于字符串长度的 1/4
时间复杂度为 O(n), 空间复杂度为 O(1)
代码:
C++:
class Solution
{
public:
int balancedString(string s)
{
int n = s.size(), target = (n >> 2), result = n, left = 0;
vector<int> count(4);
for (const auto& c : s) ++count[c == 'Q' ? 0 : (c == 'W' ? 1 : (c == 'E' ? 2 : 3))];
if (count[0] == count[1] and count[2] == count[3] and count[1] == count[2]) return left;
for (int right = 0; right < n; right++)
{
--count[s[right] == 'Q' ? 0 : (s[right] == 'W' ? 1 : (s[right] == 'E' ? 2 : 3))];
while (left <= right and count[0] <= target and count[1] <= target and count[2] <= target and count[3] <= target)
{
result = min(result, right - left + 1);
++count[s[left] == 'Q' ? 0 : (s[left] == 'W' ? 1 : (s[left] == 'E' ? 2 : 3))];
++left;
}
}
return result;
}
};
Java:
class Solution {
public int balancedString(String s) {
int n = s.length(), target = (n >> 2), result = n, left = 0, count[] = new int[4];
for (char c : s.toCharArray()) ++count[c == 'Q' ? 0 : (c == 'W' ? 1 : (c == 'E' ? 2 : 3))];
if (count[0] == count[1] && count[2] == count[3] && count[1] == count[2]) return left;
for (int right = 0; right < n; right++) {
--count[s.charAt(right) == 'Q' ? 0 : (s.charAt(right) == 'W' ? 1 : (s.charAt(right) == 'E' ? 2 : 3))];
while (left <= right && count[0] <= target && count[1] <= target && count[2] <= target && count[3] <= target) {
result = Math.min(result, right - left + 1);
++count[s.charAt(left) == 'Q' ? 0 : (s.charAt(left) == 'W' ? 1 : (s.charAt(left) == 'E' ? 2 : 3))];
++left;
}
}
return result;
}
}
Python:
class Solution:
def balancedString(self, s: str) -> int:
target, count, result, left = (n := len(s)) >> 2, Counter(s), n, 0
if count['Q'] == target and count['W'] == target and count['E'] == target and count['R'] == target:
return left
for right in range(n):
count[s[right]] -= 1
while left <= right and count['Q'] <= target and count['W'] <= target and count['E'] <= target and count['R'] <= target:
result = min(result, right - left + 1)
count[s[left]] += 1
left += 1
return result
