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^5s.length是4的倍数s中只包含Q、W、E、R四种字符由于只能替换一段连续的子串不能逐字母零散替换并且目标串长度是固定的必须与待替换子串等长因此这个问题的本质是找到最短的一个区间使得把区间内的字符重新变成任意字符后四种字符的全局频次都能恰好回到n/4。四个官方示例输入s输出说明QWER0四种字符各出现 1 次本身已平衡QQWE1把其中一个Q替换为R得到RQWE或QRWE即平衡QQQW2把前两个QQ替换为ER得到ERQW即平衡QQQQ3把最后 3 个Q替换为WER得到QWER即平衡核心思路把替换子串转化为窗口外频次约束这一题的关键一步是把问题重新表述。设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来判断窗口是否合格。双指针滑动窗口算法仓库中的解法见 源码采用双指针滑动窗口整体流程如下统计全局频次遍历一次s统计四种字符的总出现次数count并计算k len(s)/4。扩展右边界当窗口外存在某个字符频次 k即count[Q] k || count[W] k || count[E] k || count[R] k时说明当前窗口还不够大需要把右指针right向右扩展一格并把新纳入窗口的字符s[right]从全局频次表中减 1因为该字符现在属于窗口内不再属于窗口外。若右指针已经到达字符串末尾仍无法满足条件说明不可能直接跳出。收缩左边界当窗口外四种字符频次全部≤ k时当前窗口是一个合法候选。先记录right - left 1更新答案然后尝试把左指针left右移一格把s[left]归还到窗口外频次加 1看看更短的窗口是否依然合法。反复收缩直到窗口不再合法为止。持续滑动重复第 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 right1 len(s) { right count[s[right]]-- } else { break } } else { res min(res, right-left1) 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 次。超出k2的是W多 1 个和Q多 2 个。因此我们需要的替换窗口至少要能消化掉1 个W和 2 个Q——更精确地说窗口必须覆盖这 3 个多余的字符且窗口内其余字符可以任意补齐到k。这就是为什么可以用滑动窗口求覆盖指定数量字符的最短区间。窗口滑动过程如下窗口左闭右开语义下的区间窗口外频次是否合法说明0,4)即WQWRQW:1, Q:1, R:0, E:0均≤ 2合法记录长度 5尝试收缩左边界[1,4)即QWRQW:1, Q:2, R:0, E:0均≤ 2合法记录长度 4W已被踢出窗口这正是文档所说W可以踢除掉[2,4)即WRQW:2, Q:3 →Q k不合法需要继续扩右边界[2,5)即WRQQW:1, Q:2均≤ 2合法记录长度 3.........窗口继续滑动[5,8)即QQWW:1, Q:2均≤ 2合法记录长度 3末尾窗口最终最小长度为 3与仓库 [测试用例 中断言的balancedString(WQWRQQQW) 3完全一致。原文档指出这个例子中最小窗口其实位于字符串末尾的QQW把它替换为RRE之类的字符串后全局四种字符恰好各 2 次字符串恢复平衡。边界情况与易错点已经平衡的字符串QWER全局频次已经全部等于k初始窗口空窗口长度 0即合法答案0。测试用例 第一组 验证了这一点。极端失衡QQQQ中Q出现 4 次、其余为 0。平衡目标各 1 次必须替换 3 个Q答案为 3测试用例 第四组。此时窗口会一直扩展到覆盖前 3 个Q。右指针触底的退出条件当窗口外仍有字符超频但right已到len(s)-1时无法继续扩展直接break。这种情况意味着窗口已覆盖整个字符串但理论上若覆盖全串则窗口外频次全为 0必然满足≤ k因此实际运行中该分支不会成为错误答案的来源属于防御性写法。计数数组下标count用字符字节值直接作下标只适用于 ASCII 字符。题目保证输入只含四种大写字母因此安全若输入包含多字节字符如中文、emoji此写法会越界需改用 map 或哈希表。测试验证仓库为本题提供了表驱动风格的单元测试定义在 1234. Replace the Substring for Balanced String_test.go 中para1234封装输入参数sans1234封装期望答案one测试覆盖了官方示例QWER、QQWE、QQQW、QQQQ以及文档推演案例WQWRQQQW共 5 组用例每组用例调用balancedString(p.s)并断言输出。项目整体以「100% test coverage」为目标见仓库根目录 README.md 的项目描述因此该题的实现与测试均为可独立运行、可回归验证的完整单元。在 LeetCode-Go 的题目目录结构中每道题都遵循题号.题名.go题号.题名_test.goREADME.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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考