1234. 替换子串得到平衡字符串

有一个只含有 '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' 四种字

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/replace-the-substring-for-balanced-string
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

不断增加窗口右边界，寻找一个可行解，在找到可行解的情况下增加窗口左边界，优化可行解，找到最优解。
代码注释非常齐全。

代码

var balancedString = function(s) {
    const n = s.length;
    const avg = n / 4;
    const map = { Q: 0, W: 0, E: 0, R: 0};
    for (const c of s) {
        map[c]++;
    }
    if (map.Q === avg && map.W === avg && map.E === avg && map.R === avg) {
        return 0;
    }
    let minLength = n, slow = 0, fast = 0; //fast和slow形成要换的窗口
    while (fast < n) {
        const cur = s[fast]
        map[cur]--; //因为fast表示要换掉的窗口，所以遍历到这个元素就相当于这个元素要被换掉了。
        while (slow <= fast  && map.Q <= avg && map.W <= avg && map.E <= avg && map.R <= avg) { //所有 要么达到要求要么还不够，那这种时候更换窗口内的元素就一定能满足要求（因为字符串的总数一定是4的倍数）
            minLength = Math.min(minLength, fast - slow + 1);
            const slowChar = s[slow]
            map[slowChar]++ //窗口即将离开这个字符，所以这个字符不用被替换，所以++
            slow++
        }
        fast++;
    }

    return minLength
};

作者：CharleyD
链接：https://leetcode.cn/problems/replace-the-substring-for-balanced-string/solution/by-charleyd-qa0m/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。