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

Difficulty
Medium
Tags
滑动窗口
URL
https://leetcode.cn/problems/replace-the-substring-for-balanced-string/
Star
有一个只含有 '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' 四种字符
通过次数7,247提交次数20,620

法 1 华动窗口

思路
🏅
76. 最小覆盖子串 套娃题
题解
class Solution:
    def balancedString(self, s: str) -> int:
        cnt = Counter(s)
        need = collections.defaultdict(int)

        for char, val in cnt.items():
            if val > len(s) // 4:
                need[char] = val - len(s)//4
        if len(need) == 0:
            return 0
            
        # 找一个子串使得，子串中包含 need 中的字符
        l, r = 0, 0
        res = len(s)
        wds = collections.defaultdict(int)
        valid = 0
        while r < len(s):
            cur_char = s[r]
            r += 1
            if cur_char in need:
                wds[cur_char] += 1
                if wds[cur_char] == need[cur_char]:
                    valid += 1
            
            while valid == len(need):
                res = min(res, r-l)

                delet_char = s[l]
                l += 1
                if delet_char in need:
                    if wds[delet_char] == need[delet_char]:
                        valid -= 1
                    wds[delet_char] -= 1

        return res