LeetCode-Go 题解：1234. Replace the Substring for Balanced String —— 双指针滑动窗口求最小可替换子串

LeetCode-Go 题解：1234. Replace the Substring for Balanced String —— 双指针滑动窗口求最小可替换子串

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go

导读

1234. Replace the Substring for Balanced String是 LeetCode 上一道经典的滑动窗口（Sliding Window）题目：给定一个仅含'Q'、'W'、'E'、'R'四种字符、长度为 4 的倍数的字符串，要求找出「替换一个连续子串后能使整个字符串变成平衡字符串」的最小替换长度。本文以 关联文档 为骨架，结合 LeetCode-Go 仓库中的 Go 实现源码 与 测试用例，从「为什么可以转化为窗口外频次约束」的数学推导讲起，逐行拆解双指针实现，并用手跑示例验证正确性。读完本文，你将掌握一类「替换子串使全局满足某分布条件」问题的通用求解范式。

题目定义与约束

原题给出一个只含 4 种字符'Q'、'W'、'E'、'R'的字符串s，其长度为n。所谓「平衡字符串」，定义为：字符串中四种字符各自出现的次数恰好都是n/4次。

我们的任务是：返回能够被替换成任意同长度字符串、且替换后原串s变为平衡字符串的「最短子串」的长度。如果s本身已经平衡，直接返回0。

题目约束如下：

• 1 <= s.length <= 10^5
• s.length是4的倍数
• s中只包含'Q'、'W'、'E'、'R'四种字符

由于只能替换一段连续的子串（不能逐字母零散替换），并且目标串长度是固定的（必须与待替换子串等长），因此这个问题的本质是：找到最短的一个区间，使得把区间内的字符重新"变"成任意字符后，四种字符的全局频次都能恰好回到n/4。

四个官方示例

核心思路：把"替换子串"转化为"窗口外频次约束"

这一题的关键一步是把问题重新表述。设k = n/4是每个字符在平衡状态下应出现的次数。我们选定一个待替换的窗口s[left..right]，窗口之外的字符（即窗口两侧剩下的部分）是不能被修改的。

如果替换窗口内的字符后整串能平衡，那么必须满足一个充分必要条件：

窗口外的四种字符各自的出现次数都必须≤ k。

推导过程如下：

• 若某个字符c在窗口外出现次数已经> k，那么无论窗口内怎么替换（替换只会减少窗口内字符c的个数、不会影响窗口外），全局c的总数必然> k，永远无法达到平衡——因此窗口外频次> k是不可行的。
• 反之，若四个字符在窗口外的频次全部≤ k，则缺口分别为k - count_out(c)（count_out(c)为窗口外字符c的出现次数）。这些缺口的和恰好等于窗口长度right - left + 1，而窗口内的字符可以替换为任意字符串，因此只要用窗口内这right - left + 1个位置补足缺口即可，替换后四种字符恰好各k次，平衡达成。

所以，问题等价于：寻找最短的区间[left, right]，使得该区间之外四种字符的频次都不超过k。而"窗口外频次"恰好与"窗口内频次"互补：count_out(c) = total(c) - count_in(c)，因此我们可以在滑动窗口时动态维护窗口内的频次，用total(c) - count_in(c) ≤ k即count_in(c) ≥ total(c) - k来判断窗口是否"合格"。

双指针滑动窗口算法

仓库中的解法（见 源码）采用双指针滑动窗口，整体流程如下：

1. 统计全局频次：遍历一次s，统计四种字符的总出现次数count，并计算k = len(s)/4。
2. 扩展右边界：当窗口外存在某个字符频次> k（即count['Q'] > k || count['W'] > k || count['E'] > k || count['R'] > k）时，说明当前窗口还不够大，需要把右指针right向右扩展一格，并把新纳入窗口的字符s[right]从全局频次表中减 1（因为该字符现在属于"窗口内"，不再属于"窗口外"）。若右指针已经到达字符串末尾仍无法满足条件，说明不可能，直接跳出。
3. 收缩左边界：当窗口外四种字符频次全部≤ k时，当前窗口是一个合法候选。先记录right - left + 1更新答案，然后尝试把左指针left右移一格（把s[left]归还到窗口外，频次加 1），看看更短的窗口是否依然合法。反复收缩直到窗口不再合法为止。
4. 持续滑动：重复第 2、3 步直到左指针越界，期间记录到的所有合法窗口长度的最小值即为答案。

package leetcode func balancedString(s string) int { count, k := make([]int, 128), len(s)/4 for _, v := range s { count[int(v)]++ } left, right, res := 0, -1, len(s) for left < len(s) { if count['Q'] > k || count['W'] > k || count['E'] > k || count['R'] > k { if right+1 < len(s) { right++ count[s[right]]-- } else { break } } else { res = min(res, right-left+1) count[s[left]]++ left++ } } return res } func min(a int, b int) int { if a > b { return b } return a }

几点实现细节值得注意：

• count数组长度为 128，直接用字符的 ASCII 值作下标（'Q'、'W'、'E'、'R'的 ASCII 均在 128 以内），省去映射表。
• 初始时right = -1，表示窗口为空；res初始化为len(s)（最坏情况下整个串都要替换）。
• 右指针扩窗时对count[s[right]]--、左指针缩窗时对count[s[left]]++，这里维护的是窗口外（未被窗口覆盖）字符的频次，与思路推导完全一致。
• min函数在本文件内以 私有辅助函数 的形式单独定义，避免与内置库产生命名冲突。

复杂度分析

• 时间复杂度：O(n)。左、右指针各自最多移动n次，整体是线性扫描。
• 空间复杂度：O(1)。只使用了固定大小的频次数组（128 个int）。

手跑示例："WQWRQQQW"

原文档用"WQWRQQQW"作为推演案例，这里完整复现一遍。字符串长度n = 8，因此k = 2，平衡状态下每个字符应恰好出现 2 次。

全局统计：W出现 3 次，Q出现 4 次，R出现 1 次，E出现 0 次。超出k=2的是W（多 1 个）和Q（多 2 个）。因此我们需要的替换窗口，至少要能"消化"掉1 个W和 2 个Q——更精确地说，窗口必须覆盖这 3 个多余的字符，且窗口内其余字符可以任意补齐到k。这就是为什么可以用滑动窗口求"覆盖指定数量字符的最短区间"。

窗口滑动过程如下：

最终最小长度为 3，与仓库 [测试用例 中断言的balancedString("WQWRQQQW") == 3完全一致。原文档指出，这个例子中最小窗口其实位于字符串末尾的"QQW"：把它替换为"RRE"之类的字符串后，全局四种字符恰好各 2 次，字符串恢复平衡。

边界情况与易错点

1. 已经平衡的字符串："QWER"全局频次已经全部等于k，初始窗口（空窗口，长度 0）即合法，答案0。测试用例 第一组 验证了这一点。
2. 极端失衡："QQQQ"中Q出现 4 次、其余为 0。平衡目标各 1 次，必须替换 3 个Q，答案为 3（测试用例 第四组）。此时窗口会一直扩展到覆盖前 3 个Q。
3. 右指针触底的退出条件：当窗口外仍有字符超频但right已到len(s)-1时无法继续扩展，直接break。这种情况意味着窗口已覆盖整个字符串，但理论上若覆盖全串则窗口外频次全为 0，必然满足≤ k，因此实际运行中该分支不会成为错误答案的来源，属于防御性写法。
4. 计数数组下标：count用字符字节值直接作下标，只适用于 ASCII 字符。题目保证输入只含四种大写字母，因此安全；若输入包含多字节字符（如中文、emoji），此写法会越界，需改用 map 或哈希表。

测试验证

仓库为本题提供了表驱动风格的单元测试，定义在 1234. Replace the Substring for Balanced String_test.go 中：

• para1234封装输入参数s，ans1234封装期望答案one；
• 测试覆盖了官方示例"QWER"、"QQWE"、"QQQW"、"QQQQ"以及文档推演案例"WQWRQQQW"，共 5 组用例；
• 每组用例调用balancedString(p.s)并断言输出。

项目整体以「100% test coverage」为目标（见仓库根目录 README.md 的项目描述），因此该题的实现与测试均为可独立运行、可回归验证的完整单元。在 LeetCode-Go 的题目目录结构中，每道题都遵循"题号.题名.go+题号.题名_test.go+README.md"的三件套约定（如 1234 题目录），读者可参考这一模式在本地go test验证任意一题的解法。

小结

1234 题的核心价值在于一个漂亮的等价转化：「替换一段子串使全局平衡」≡「找最短区间，使区间之外四种字符频次都不超过k」。基于这一转化，双指针滑动窗口可以在 O(n) 时间内完成扫描：右指针负责"补足"，左指针负责"试探收缩"，所有合法窗口长度的最小值即为答案。这种"用窗口外频次约束代替窗口内内容约束"的思路，同样适用于一类"通过替换/覆盖使全局满足分布条件"的题目，是滑动窗口家族中值得反复体会的代表作。

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go