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(n2) 優化到 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 滑動窗口解法深度解析
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(n2) 優化到 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），僅供參考