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

2023-09-07 HGNULB 约 6 分钟

文章信息 6 个分类 · 2 个标签

分类

LeetCode CodeTop 中等 未解决 1-2 阿里

标签

字符串 滑动窗口

题目描述

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

题意分析

字符串只包含 Q、W、E、R，长度 n 是四的倍数。可以选择一个连续子串，将它替换成任意一个等长字符串，使最终四种字符都恰好出现 n / 4 次，求最短的替换长度。

被选中的子串内部可以全部重新安排，子串外的字符不能改变，也不能选择若干不连续的位置合并替换。若原串已经平衡，允许不替换，答案为零；题目只需要长度，不要求构造替换内容。

解法：滑动窗口维护有效区间

核心思路

[!blue]

把待替换的连续子串看成一个窗口，关注不能修改的窗口外部分。若外面某种字符已经超过 target = n / 4，无论窗口内改成什么，都无法减少外面的超额字符，所以这个窗口一定不可行。

反过来，如果窗口外四种字符都不超过目标，窗口就一定可行。每种字符还需要补入 target - 外部数量 个，这些缺口都非负；四种缺口总和等于 4 * target - 窗口外长度，也就是窗口长度。因此窗口内部恰好可以填满这些缺口，让整串平衡。这证明了外部不超额既必要又充分。

用 cnt 始终统计窗口外的数量。初始窗口为空，所以先统计整串。右端加入字符时，这个字符从不可修改部分进入可替换部分，外部计数减一；左端离开窗口时，它重新成为不能修改的字符，计数加回。

右端不断扩张，直到外部四种计数都不超额。窗口合法时，先记录当前长度，再持续右移左端尝试缩短；一旦外部重新超额，暂停收缩，继续扩大右端。这里求最短窗口，所以是合法时收缩，而不是等非法时才缩短。

已经移过的左端不需要回退：它在此前的某个右端已经形成过合法窗口并被记录，之后右端更靠右，只会让同一左端对应的窗口更长，不可能改善最小值。两个边界因此都可以单向前进。

原串已经平衡时，空窗口就是最优解，应直接返回零。否则整串替换总能满足要求，所以把初始答案设为 n，再通过窗口逐步缩短。

解题步骤

1. 统计四种字符总数，设每种目标为 n / 4；原串已平衡则返回零。
2. 枚举右端，把进入窗口的字符从外部计数中减一。
3. 当四种外部计数都不超过目标时，记录当前窗口长度。
4. 将左端字符加回外部计数并推进左端，继续尝试收缩，直到窗口不再合法。
5. 扫描全部右端后返回最短长度。

代码实现

class Solution {
    public int balancedString(String s) {
        int n = s.length();
        int target = n / 4;
        // 窗口初始为空，计数表示整个窗口外的字符数量。
        int[] cnt = new int[128];

        for (int i = 0; i < n; i++) {
            cnt[s.charAt(i)]++;
        }

        if (cnt['Q'] <= target && cnt['W'] <= target && cnt['E'] <= target && cnt['R'] <= target) {
            return 0;
        }

        int answer = n;
        int left = 0;

        for (int right = 0; right < n; right++) {
            // 字符进入替换窗口，从窗口外计数中扣除。
            cnt[s.charAt(right)]--;

            while (left <= right
                    && cnt['Q'] <= target
                    && cnt['W'] <= target
                    && cnt['E'] <= target
                    && cnt['R'] <= target) {
                // 当前窗口合法，先记录长度再尝试收缩。
                answer = Math.min(answer, right - left + 1);
                // 左端字符离开窗口，重新计入窗口外。
                cnt[s.charAt(left)]++;
                left++;
            }
        }

        return answer;
    }
}

func balancedString(s string) int {
    n := len(s)
    target := n / 4
    // 窗口初始为空，计数表示整个窗口外的字符数量。
    cnt := make([]int, 128)
    for i := 0; i < n; i++ {
        cnt[s[i]]++
    }

    if cnt['Q'] <= target && cnt['W'] <= target && cnt['E'] <= target && cnt['R'] <= target {
        return 0
    }

    answer := n
    left := 0
    for right := 0; right < n; right++ {
        // 字符进入替换窗口，从窗口外计数中扣除。
        cnt[s[right]]--

        for left <= right && cnt['Q'] <= target && cnt['W'] <= target && cnt['E'] <= target && cnt['R'] <= target {
            // 当前窗口合法，先记录长度再尝试收缩。
            if right-left+1 < answer {
                answer = right - left + 1
            }
            // 左端字符离开窗口，重新计入窗口外。
            cnt[s[left]]++
            left++
        }
    }
    return answer
}

复杂度分析

• 时间复杂度：$O(n)$，初始计数扫描一次，左右边界之后各最多移动 n 次，每次只检查四种字符的计数。
• 空间复杂度：$O(1)$，保存固定大小计数表、窗口边界及答案，不生成候选替换字符串。

关键点总结

[!green]

• 可替换部分不必直接满足某种分布，只需不可修改的窗口外部分不再超额。
• 缺口非负且总数恰好等于窗口长度，保证能够构造合法替换内容。
• cnt 表示窗口外，进窗减、出窗加；合法时先记录再缩短。

易错点总结

[!yellow]

• 把 cnt 当成窗口内频次，会把更新方向与合法性条件全部颠倒。
• 只检查某一种超额字符，没有确保四种外部计数都不超过目标，可能遗漏其他无法修复的超额部分。
• 合法后只缩一次，可能漏掉同一右端下更短的可行窗口，应持续尝试。
• 先移出左端再记录，新的窗口可能已经失效，应在原窗口合法时先记录长度。
• 忘记移出时加回外部计数，会低估不可修改部分的数量，产生错误的过短答案。
• 没有处理原串已平衡的情况，只扫描非空窗口就可能漏掉答案零。

相似题目

题目	难度	关联与区别
76. 最小覆盖子串	困难	需要替换的窗口至少覆盖各字母超额部分，可转成最小覆盖窗口的频次条件。
424. 替换后的最长重复字符	中等	同样用窗口改变字符分布，本题目标是四类字符各占四分之一，原题目标是窗口内统一字符。

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2023/61216580

许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！