企业官网建设流程全解析

LeetCode-Go 题解：1208. Get Equal Substrings Within Budget 滑动窗口解法深度解析

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

本篇文章以 LeetCode-Go 仓库中 1208.Get-Equal-Substrings-Within-Budget/README.md 为骨架，结合该题目的 Go 源码实现与单元测试，完整讲解「预算内最长可转换子串」问题的滑动窗口（双指针）解法。读完本文，你将掌握如何把"最大连续子数组"类问题转化为"滑动窗口 + 预算增减"模型，并能直接在 Go 中写出 100% 测试覆盖的 AC 代码。

题目原文

给定两个长度相同的字符串s和t。将s中的第i个字符变成t中的第i个字符，需要花费|s[i] - t[i]|，即两个字符 ASCII 码值之差的绝对值。

再给定一个整数maxCost（预算）。

返回s中能转换成与t对应子串相同、且总花费不超过maxCost的最长子串长度。

如果s中不存在任何能转换成t中对应子串的子串，返回0。

示例

示例 1：

Input: s = "abcd", t = "bcdf", maxCost = 3 Output: 3 Explanation: "abc" of s can change to "bcd". That costs 3, so the maximum length is 3.

解释：s = "abcd"与t = "bcdf"逐位计算开销：|a-b|=1、|b-c|=1、|c-d|=1、|d-f|=2。取前三位的累计开销恰好为3，因此最长可转换子串长度为3。

示例 2：

Input: s = "abcd", t = "cdef", maxCost = 3 Output: 1 Explanation: Each character in s costs 2 to change to charactor in t, so the maximum length is 1.

解释：每一位的开销均为|a-c|=2、|b-d|=2、|c-e|=2、|d-f|=2。预算3不足以覆盖两个字符（2+2=4 > 3），因此最长长度为1。

示例 3：

Input: s = "abcd", t = "acde", maxCost = 0 Output: 1 Explanation: You can't make any change, so the maximum length is 1.

解释：预算为0，只有开销为0的字符位才能"免费"转换。第一位|a-a|=0满足条件，其余位均有开销，因此最长长度为1。

约束条件

• 1 <= s.length, t.length <= 10^5
• 0 <= maxCost <= 10^6
• s和t只包含小写英文字母

题目大意（中文解读）

给你两个长度相同的字符串s和t，将s中的第i个字符变到t中的第i个字符需要|s[i] - t[i]|的开销（开销可能为 0），也就是两个字符 ASCII 码值的差的绝对值。

用于变更字符串的最大预算是maxCost。在转化字符串时，总开销应当小于等于该预算，这也意味着字符串的转化可能是不完全的。如果你可以将s的子字符串转化为它在t中对应的子字符串，则返回可以转化的最大长度。如果s中没有子字符串可以转化成t中对应的子字符串，则返回0。

解题思路：滑动窗口（双指针）

核心模型：把"预算"当作窗口容量

这一题给出 2 个字符串s、t和一个"预算"，要求把"预算"尽可能花完，求s中最多连续有几个字母能变成t中的字母。"预算"的定义是|s[i] - t[i]|。

这是一个典型的最长连续子数组问题，满足"单调性"：窗口越大，累计开销只增不减。因此可以用滑动窗口（可变窗口双指针）在线性时间内求解：

1. 右边界扩张：滑动窗口右边界每移动一格，就消耗一定的预算（减去|s[right] - t[right]|）；
2. 左边界收缩：当预算不足以容纳新字符时（maxCost - cost < 0），移动滑动窗口左边界，把左侧字符的开销还原回去（加回|s[left] - t[left]|），直到预算重新满足条件；
3. 统计答案：当整个窗口把字符s或t都滑动完了的时候，取出滑动过程中窗口的最大值即为结果。

单调性的正确性依据

• 每一位的转换开销|s[i] - t[i]| >= 0，非负；
• 因此对于任意固定左边界left，随着右边界right增大，窗口内累计开销单调不减；
• 一旦累计开销超过maxCost，必须收缩左边界；左边界收缩后累计开销单调不增；
• 所以"能容纳的开销 <= maxCost 的最长窗口"可以用双指针线性求解，不需要对每个起点做二分或暴力枚举。

仓库源码级实现解析

仓库中的核心实现位于 1208. Get Equal Substrings Within Budget.go，完整代码如下：

package leetcode func equalSubstring(s string, t string, maxCost int) int { left, right, res := 0, -1, 0 for left < len(s) { if right+1 < len(s) && maxCost-abs(int(s[right+1]-'a')-int(t[right+1]-'a')) >= 0 { right++ maxCost -= abs(int(s[right]-'a') - int(t[right]-'a')) } else { res = max(res, right-left+1) maxCost += abs(int(s[left]-'a') - int(t[left]-'a')) left++ } } return res } func max(a int, b int) int { if a > b { return a } return b } func abs(a int) int { if a > 0 { return a } return -a }

关键实现细节逐行拆解

1. 指针初始化

left, right, res := 0, -1, 0

• left从0开始；right初始化为-1，表示窗口为空；
• res记录历史最大窗口长度，初始为0（对应"没有任何子串可转换"时的答案）。

2. 右边界尝试扩张

if right+1 < len(s) && maxCost-abs(int(s[right+1]-'a')-int(t[right+1]-'a')) >= 0 { right++ maxCost -= abs(int(s[right]-'a') - int(t[right]-'a')) }

• 先检查right+1是否越界，再计算把s[right+1]转成t[right+1]的开销；
• 若剩余预算足以支付该开销，则右边界前进一格并扣减预算；
• 注意这里先将s/t字符减去'a'再取差，虽然因为|s[i]-t[i]|是绝对差，直接相减效果相同，但统一到0..25的字母序号区间，语义更清晰、可读性更好。

3. 左边界收缩 + 统计答案

res = max(res, right-left+1) maxCost += abs(int(s[left]-'a') - int(t[left]-'a')) left++

• 当右边界无法继续扩张（越界或预算不足）时，先记录当前窗口长度right-left+1更新res；
• 再把左边字符的开销归还给预算（加回|s[left]-t[left]|），左边界left++；
• 循环回到第 2 步继续尝试右边界扩张，形成"右进左退"的窗口滑动。

4. 边界情况

• 若某一位转换开销本身就大于maxCost（例如示例 3 中预算为 0 且该位开销非 0），右边界无法扩张，res更新为max(res, right-left+1)。此时right+1 == left（窗口为单个字符left），窗口长度right-left+1计算正确；
• 当所有字符都无法转换时，res保持为 0，符合题目"返回 0"的要求。

复杂度分析

• 时间复杂度：O(n)，其中n = len(s)。left和right各自最多移动n次，总移动次数不超过2n，属于标准的线性滑动窗口复杂度；
• 空间复杂度：O(1)，只使用了left、right、res三个整数变量，没有任何辅助数据结构。

在1 <= s.length, t.length <= 10^5的约束下，O(n) 的滑动窗口是本题的最优解之一。

测试用例验证

仓库提供了配套的单元测试 1208. Get Equal Substrings Within Budget_test.go，覆盖了题目给出的 3 个示例以及 2 组额外用例：

测试采用表驱动（table-driven）风格：用para1208结构体承载参数s、t、maxCost，用ans1208结构体承载期望答案one，每个用例调用equalSubstring(p.s, p.t, p.maxCost)并打印输入与输出，方便对照验证。

例如额外用例s = "krrgw", t = "zjxss", maxCost = 19：逐位开销为|k-z|=15、|r-j|=8、|r-x|=5、|g-s|=12、|w-s|=4。预算 19 下，能容纳开销不超过 19 的最长连续子串长度为 2（如|r-x|=5与|g-s|=12合计 17，或|r-j|=8与|r-x|=5合计 13），与期望输出 2 一致。

如何运行测试

仓库根目录是 Go module（见 go.mod，module 名为github.com/halfrost/LeetCode-Go，Go 版本 1.19），可直接在任意题解目录下运行：

# 单题测试（带详细输出） go test -v ./leetcode/1208.Get-Equal-Substrings-Within-Budget/ # 全部题解测试 go test ./leetcode/...

仓库的 gotest.sh 展示了全量覆盖率测试的标准做法：

go test -covermode=atomic -coverprofile=coverage.txt ./leetcode/...

该脚本会对整个leetcode目录生成原子模式（atomic）的覆盖率报告，与仓库"100% test coverage"的目标保持一致——本题的equalSubstring同样有完整测试覆盖。

思路延伸：滑动窗口模板化

本题是滑动窗口（Sliding Window）的经典代表，其"右边界扩张扣预算、左边界收缩还预算"的模式可以抽象为通用模板，适用于「最长连续子数组满足某条件」类问题：

left, right := 0, -1 res := 0 for left < len(s) { // 1. 尝试扩张右边界：若加入新元素后仍满足约束 if right+1 < len(s) && 满足约束条件(right+1) { right++ // 更新窗口状态（扣减预算 / 增加计数等） } else { // 2. 记录当前窗口对答案的贡献 res = max(res, right-left+1) // 3. 收缩左边界：还原窗口状态（归还预算 / 减少计数等） left++ } } return res

同一模板稍加改动即可套用到其他题目，例如：

• 最大连续 1 的个数 III（可翻转最多 k 个 0）：把"0 的个数"当作预算；
• 替换后的最长重复字符：把"非众数字符的个数"当作预算；
• 无重复字符的最长子串：把"字符出现次数"当作约束条件。

掌握"预算扣减/归还"这一对操作，就抓住了可变窗口滑动窗口的精髓：窗口内状态随右边界进入而消耗，随左边界离开而恢复，答案在所有合法窗口长度的最大值中产生。

小结

LeetCode 1208 题的 Go 解法核心可以总结为三点：

1. 问题本质：求满足"累计开销 <= maxCost"的最长连续子数组长度；
2. 算法选择：因开销非负、窗口开销单调，采用滑动窗口（双指针）可将暴力 O(n²) 优化到 O(n) 时间、O(1) 空间；
3. 工程实践：仓库中的 源码实现 与 表驱动测试 可直接复制运行，是面试与刷题时值得反复对照的模板。

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