LeetCode-Go 题解：1208. Get Equal Substrings Within Budget 滑动窗口解法深度解析-北京尧图网络

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。示例示例 1Input: 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。示例 2Input: 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不足以覆盖两个字符224 3因此最长长度为1。示例 3Input: s abcd, t acde, maxCost 0 Output: 1 Explanation: You cant make any change, so the maximum length is 1.解释预算为0只有开销为0的字符位才能免费转换。第一位|a-a|0满足条件其余位均有开销因此最长长度为1。约束条件1 s.length, t.length 10^50 maxCost 10^6s和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]|。这是一个典型的最长连续子数组问题满足单调性窗口越大累计开销只增不减。因此可以用滑动窗口可变窗口双指针在线性时间内求解右边界扩张滑动窗口右边界每移动一格就消耗一定的预算减去|s[right] - t[right]|左边界收缩当预算不足以容纳新字符时maxCost - cost 0移动滑动窗口左边界把左侧字符的开销还原回去加回|s[left] - t[left]|直到预算重新满足条件统计答案当整个窗口把字符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 right1 len(s) maxCost-abs(int(s[right1]-a)-int(t[right1]-a)) 0 { right maxCost - abs(int(s[right]-a) - int(t[right]-a)) } else { res max(res, right-left1) 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, 0left从0开始right初始化为-1表示窗口为空res记录历史最大窗口长度初始为0对应没有任何子串可转换时的答案。2. 右边界尝试扩张if right1 len(s) maxCost-abs(int(s[right1]-a)-int(t[right1]-a)) 0 { right maxCost - abs(int(s[right]-a) - int(t[right]-a)) }先检查right1是否越界再计算把s[right1]转成t[right1]的开销若剩余预算足以支付该开销则右边界前进一格并扣减预算注意这里先将s/t字符减去a再取差虽然因为|s[i]-t[i]|是绝对差直接相减效果相同但统一到0..25的字母序号区间语义更清晰、可读性更好。3. 左边界收缩统计答案res max(res, right-left1) maxCost abs(int(s[left]-a) - int(t[left]-a)) left当右边界无法继续扩张越界或预算不足时先记录当前窗口长度right-left1更新res再把左边字符的开销归还给预算加回|s[left]-t[left]|左边界left循环回到第 2 步继续尝试右边界扩张形成右进左退的窗口滑动。4. 边界情况若某一位转换开销本身就大于maxCost例如示例 3 中预算为 0 且该位开销非 0右边界无法扩张res更新为max(res, right-left1)。此时right1 left窗口为单个字符left窗口长度right-left1计算正确当所有字符都无法转换时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 组额外用例stmaxCost期望输出abcdbcdf33abcdcdef31abcdacde01thjdoffkaqhrnlntls113krrgwzjxss192测试采用表驱动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.modmodule 名为github.com/halfrost/LeetCode-GoGo 版本 1.19可直接在任意题解目录下运行# 单题测试带详细输出 go test -v ./leetcode/1208.Get-Equal-Substrings-Within-Budget/ # 全部题解测试 go test ./leetcode/...仓库的 gotest.sh 展示了全量覆盖率测试的标准做法go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...该脚本会对整个leetcode目录生成原子模式atomic的覆盖率报告与仓库100% test coverage的目标保持一致——本题的equalSubstring同样有完整测试覆盖。思路延伸滑动窗口模板化本题是滑动窗口Sliding Window的经典代表其右边界扩张扣预算、左边界收缩还预算的模式可以抽象为通用模板适用于「最长连续子数组满足某条件」类问题left, right : 0, -1 res : 0 for left len(s) { // 1. 尝试扩张右边界若加入新元素后仍满足约束 if right1 len(s) 满足约束条件(right1) { right // 更新窗口状态扣减预算 / 增加计数等 } else { // 2. 记录当前窗口对答案的贡献 res max(res, right-left1) // 3. 收缩左边界还原窗口状态归还预算 / 减少计数等 left } } return res同一模板稍加改动即可套用到其他题目例如最大连续 1 的个数 III可翻转最多 k 个 0把0 的个数当作预算替换后的最长重复字符把非众数字符的个数当作预算无重复字符的最长子串把字符出现次数当作约束条件。掌握预算扣减/归还这一对操作就抓住了可变窗口滑动窗口的精髓窗口内状态随右边界进入而消耗随左边界离开而恢复答案在所有合法窗口长度的最大值中产生。小结LeetCode 1208 题的 Go 解法核心可以总结为三点问题本质求满足累计开销 maxCost的最长连续子数组长度算法选择因开销非负、窗口开销单调采用滑动窗口双指针可将暴力 O(n²) 优化到 O(n) 时间、O(1) 空间工程实践仓库中的源码实现与表驱动测试可直接复制运行是面试与刷题时值得反复对照的模板。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考

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

相关推荐

基于Python的财务信用分析与评分卡建模全流程解析

SpringBoot+微信小程序流浪动物救助系统：状态流转与并发控制实战

.NET 8 Web API 项目源码设计：从骨架到鉴权与可靠性验证

更多资讯

JSP+Servlet+MySQL学生选课系统实战

SSM就业平台：岗位智能匹配与MySQL索引优化实战

CookLikeHOC 复刻指南：剁椒鱼头（草鱼头版）——配料标准、蒸制工艺与营养成分全解析

锂离子电池Simulink建模与配置优化指南

网络安全靶场训练指南：从入门到实战

智能鱼塘溶氧监测系统设计与实现

今日更新

SpacetimeDB C++ 模块库实战：用 C++20 在数据库内构建 WebAssembly 模块

别踩雷！不是所有 AI 写作工具都靠谱，2026 高校认可工具精选

SSM+MySQL幼儿园管理系统源码解析：从部署到优化

本周精选

超人会飞不算本事：系统稳定依赖清晰规则与边界设计

超人VS蜘蛛侠：拆解超级IP的影响力与传播方法论

基于CNN的调制信号识别：MATLAB实现时频图分类实战

本月热门

基于YOLO的焊缝缺陷检测：从数据标注到工业部署全流程实践

分布式服务的决策记录

创业产品的首版范围

读完文章，想聊聊您的网站？