1234. 替换子串得到平衡字符串 Medium
有一个只含有 '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"。
解题思路
输入： 一个只包含 QWER 的字符串 s，可以将任意子串替换成任何其他字符串来变成 平衡字符串
输出： 返回替换字串的最小可能长度
本题属于 可变长度滑动窗口类型 类型。
我们可以逆向思考，找出一个最短的窗口，窗口内的值可以换成任何字符，剩下的字符保证是平衡的就行
换句话说，我们想找一个最小窗口 [l, r]，使得：在这个窗口外（即 s[:l] + s[r+1:]）的字符都 <= n // 4
为什么是 <= n // 4，因为 窗口长度一定 ≥ 所有超额字符的总数
代码实现
python
class Solution:
def balancedString(self, s: str) -> int:
n = len(s)
expected = n // 4 # 每个字符应有的数量（平衡时）
# 初始化字符频率计数器
freq = {'Q': 0, 'W': 0, 'E': 0, 'R': 0}
# 统计整个字符串中 QWER 出现的频率
for ch in s:
freq[ch] += 1
# 如果已经是平衡字符串，直接返回 0（不需要替换任何子串）
if all(freq[c] == expected for c in "QWER"):
return 0
ans = n # 初始化最小子串长度为最大值
left = 0 # 滑动窗口左指针
# 滑动窗口右指针从 0 开始遍历整个字符串
for right in range(len(s)):
freq[s[right]] -= 1 # 将当前字符“视为替换掉”，频率减少
# 如果窗口外的字符频率都不超过 expected，说明剩下的部分已经满足要求
while left < n and all(freq[c] <= expected for c in "QWER"):
# 更新最小窗口长度
ans = min(ans, right - left + 1)
# 移动左指针（即恢复左边字符的频率）
freq[s[left]] += 1
left += 1
return ans # 返回最短可替换子串长度javascript
/**
* @param {string} s
* @return {number}
*/
var balancedString = function(s) {
// 每个字符应该出现的次数（总长度 / 4）
const target = s.length / 4;
// 用数组统计 Q W E R 出现的次数
// 下标映射: Q=0, W=1, E=2, R=3
const freq = [0, 0, 0, 0];
const map = { Q: 0, W: 1, E: 2, R: 3 };
// 先统计整个字符串的频率
for (let ch of s) {
freq[map[ch]]++;
}
// 如果一开始就已经平衡，不需要替换
if (freq[0] === target && freq[1] === target && freq[2] === target && freq[3] === target) {
return 0;
}
let left = 0; // 滑动窗口的左指针
let ans = s.length; // 结果（最小子串长度）
// 判断当前 freq 是否满足平衡条件：
// 也就是说剩下的所有字符都 <= target
const check = () =>
freq[0] <= target &&
freq[1] <= target &&
freq[2] <= target &&
freq[3] <= target;
// 移动右指针，逐个把字符“拿进窗口”
for (let right = 0; right < s.length; right++) {
// 当前字符计数 -1，表示它已经被“替换”进窗口
freq[map[s[right]]]--;
// 如果此时已经满足平衡条件，就尝试收缩左边界
while (left < s.length && check()) {
// 更新最优解（最小子串长度）
ans = Math.min(ans, right - left + 1);
// 左指针右移，相当于把一个字符“吐出来”，恢复计数
freq[map[s[left]]]++;
left++;
}
}
return ans;
};复杂度分析
时间复杂度：O(n)
空间复杂度：O(1)