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

难度

• Easy
• Medium
• Hard

思路

一开始没审清题意，题目要求的是替换连续子串。

1. 要让字符串平衡，一定是需要替换每个字母多于平均值的部分。
2. 要求连续子串，也就是要找到包含了规定数量的需要替换字母的最短连续子串。
3. 连续子数组、子串问题，可以使用不定长滑动窗口（双指针）来解决。枚举右端点，不断收缩左端点。

代码

class Solution:
    def balancedString(self, s: str) -> int:
        left = 0
        ans = inf
        # 滑动窗口时统计使用
        cnt = Counter()
        # 记录需要的字母数量
        need = Counter()
        average = len(s) // 4
        for c in "QWER":
            need[c] = max(0, s.count(c) - average)
        # 如果已经平衡，直接返回
        if need['Q'] == 0 and need['W'] == 0 and need['E'] == 0 and need['R'] == 0:
            return 0
        # 枚举右端点
        for right, c in enumerate(s):
            cnt[c] += 1
            # 如果去掉左端点字母依然满足所需数量，则向右收缩
            while left <= right and cnt[s[left]] - 1 >= need[s[left]]:
                cnt[s[left]] -= 1
                left += 1
            # 仅当当前窗口满足所有数量要求时更新 ans
            if right >= left and cnt['Q'] >= need['Q'] and cnt['W'] >= need['W'] and cnt['E'] >= need['E'] and cnt['R'] >= need['R']:
                ans = min(ans, right -left + 1)
        return ans