LeetCode-Go 题解1209. Remove All Adjacent Duplicates in String IIk 倍重复项删除栈计数法【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go本篇指南围绕 LeetCode 第 1209 题「Remove All Adjacent Duplicates in String II」展开结合 LeetCode-Go 仓库中的完整实现与测试用例讲解「k 倍重复项删除」问题的暴力解法与栈计数解法的原理、复杂度差异与 Go 代码细节。读完本文你将掌握如何用「栈 频次计数」在 O(n) 时间内解决这一类「相邻重复消除消消乐」问题并能直接复用仓库中可运行、可验证的 Go 源码。题目描述与约束给定一个字符串s一次k 倍重复项删除操作k duplicate removal指从s中选择k个相邻且相等的字母并删除它们使被删子串左侧和右侧的字符串重新拼接在一起。反复对s执行该操作直到无法继续删除为止返回最终字符串。题目保证最终答案唯一。约束条件如下1 s.length 10^52 k 10^4s仅包含小写英文字母示例分析示例 1Input: s abcd, k 2 Output: abcd字符串中不存在任何两个相邻且相等的字母无需删除。示例 2Input: s deeedbbcccbdaa, k 3 Output: aa删除过程分步如下先删除eee与ccc得到ddbbbdaa再删除bbb得到dddaa最后删除ddd得到aa。示例 3Input: s pbbcggttciiippooaais, k 2 Output: ps注意示例 3 中k 2这正是 1047. Remove All Adjacent Duplicates In String 的特殊情形每遇到两个相邻相同字符即消除。本题将其泛化到了任意k 2。解题思路一暴力扫描消消乐式反复消除最直观的做法是边读边消每追加一个字符就向前扫描统计以末尾字符结尾的连续相同字符个数一旦达到k个便整体切除。被切除后拼接形成的新字符串尾部可能再次出现k个相同字符因此需要循环检查直到尾部不再满足消除条件——这正是「消消乐」中碰撞即消除的过程。仓库中该解法对应 1209. Remove All Adjacent Duplicates in String II.go 中的removeDuplicates1// 解法二 暴力 func removeDuplicates1(s string, k int) string { arr, count, tmp : []rune{}, 0, # for _, v : range s { arr append(arr, v) for len(arr) 0 { count 0 tmp arr[len(arr)-1] for i : len(arr) - 1; i 0; i-- { if arr[i] ! tmp { break } count } if count k { arr arr[:len(arr)-k] } else { break } } } return string(arr) }该实现的核心机制使用[]rune切片模拟可变的字符串尾部逐个追加字符内层循环从末尾向前数出连续相同字符的个数count若count k执行arr arr[:len(arr)-k]切除末尾k个字符切除后继续回到内层循环开头重新统计新末尾的连续相同字符数直至不再满足消除条件才跳出。复杂度与瓶颈时间复杂度最坏情况下每次消除后都需要重新向前统计整体达到O(n²)空间复杂度O(n)用于存放拼接结果。低效的根源在于重复统计字符频次同一段连续相同字符可能被反复从后往前计数尤其是消除后又拼接出新的相同块时统计工作被一遍遍重做。解题思路二栈 频次计数O(n) 解法暴力解法的问题在于「每次都要重新数数」。如果每个字符的频次只统计一次就能把复杂度降下来。做法是使用一个栈每个栈元素存两个值字符本身以及该字符当前的连续出现频次。有了栈顶的频次信息就无需再向前回溯扫描每当栈顶字符与待入栈字符相同就只把栈顶频次加 1一旦栈顶频次达到k说明栈顶这一段刚好构成k个相邻且相等的字符直接弹出该元素即可。如此反复最终栈中剩下的就是所求字符串。栈解法 Go 实现仓库中的removeDuplicates即栈解法package leetcode // 解法一 stack func removeDuplicates(s string, k int) string { stack, arr : [][2]int{}, []byte{} for _, c : range s { i : int(c - a) if len(stack) 0 stack[len(stack)-1][0] i { stack[len(stack)-1][1] if stack[len(stack)-1][1] k { stack stack[:len(stack)-1] } } else { stack append(stack, [2]int{i, 1}) } } for _, pair : range stack { c : byte(pair[0] a) for i : 0; i pair[1]; i { arr append(arr, c) } } return string(arr) }逐步拆解这段代码栈结构stack的类型为[][2]int每个元素pair[0]存字符索引c - a即 025pair[1]存该字符当前的连续出现次数入栈逻辑新字符与栈顶字符不同或栈为空时压入[2]int{i, 1}频次从 1 开始计数与消除新字符与栈顶相同时仅stack[len(stack)-1][1]当频次累计到k说明栈顶已经形成k个相邻相同字符直接stack stack[:len(stack)-1]弹出整个元素。由于元素弹出后新的栈顶可能又是相同字符且此前频次已被记录过因此无需回溯天然支持连续消除如示例 2 中dddd依次消去一组ddd后剩下的d与后续字符的衔接重组结果扫描结束后遍历栈中剩余元素按pair[0] a还原字符并按pair[1]的频次展开拼入arr最终string(arr)即为答案。为什么它能做到 O(n)关键在于每个栈元素只入栈、出栈各一次字符一旦被压入栈其频次在栈顶时被原地累加达到k时整块弹出之后不会再被重新统计。相比暴力解法的反复向前计数这种「计数前置、消除后无需回溯」的设计将复杂度稳定在时间复杂度O(n)每个字符处理常数次空间复杂度O(n)栈最大深度为字符串长度。测试用例与验证仓库为本题配套了测试文件 1209. Remove All Adjacent Duplicates in String II_test.go采用本仓库统一的「问题描述结构体 参数/答案表」风格type para1209 struct { s string k int } type ans1209 struct { one string } func Test_Problem1209(t *testing.T) { qs : []question1209{ { para1209{deeedbbcccbdaa, 3}, ans1209{aa}, }, { para1209{pbbcggttciiippooaais, 2}, ans1209{ps}, }, } // ... }测试覆盖了题目给出的示例 2k 3与示例 3k 2并在循环中同时调用removeDuplicates与removeDuplicates1两种实现进行对比验证确保栈解法与暴力解法结果一致。若要运行整个仓库的全部测试可参照根目录的 gotest.shgo test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...其中-coverprofilecoverage.txt用于产出统一的覆盖率文件针对单个题目可在对应目录下执行go test -v -run Test_Problem1209与 1047 题的关联k 2 特例本题是 1047. Remove All Adjacent Duplicates In String 的推广1047 题固定删除 2 个相邻相同字符其实现1047. Remove All Adjacent Duplicates In String.go只用一个[]rune栈遇到与栈顶相同的字符即弹出func removeDuplicates1047(S string) string { stack : []rune{} for _, s : range S { if len(stack) 0 || len(stack) 0 stack[len(stack)-1] ! s { stack append(stack, s) } else { stack stack[:len(stack)-1] } } return string(stack) }对比可见1209 题的栈解法就是在 1047 题「字符栈」的基础上为每个栈元素附加了一个「频次」维度从而把「固定消 2 个」推广为「任意消 k 个」。理解了这一层演化关系就能把两题当作同一类「相邻重复消除」模型来记忆用栈保存字符与计数命中即消除消除后无需回溯。小结解法核心思想时间复杂度空间复杂度仓库实现暴力扫描追加字符后向前统计连续相同个数达到 k 即切除并循环检查O(n²)O(n)removeDuplicates1栈 频次栈元素存字符频次栈顶频次达 k 即弹出O(n)O(n)removeDuplicates面对s.length上限达 10⁵ 的输入规模O(n²) 的暴力解法存在超时风险栈计数法是本题的推荐实现一次扫描、计数前置、消除后免回溯既简洁又高效。该解法与 1047 题 一脉相承可作为面试中「相邻消除」类题目的通用模板直接套用。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 
长河君 · 2026/9/12 22:30:24 · 阅读 1.2k LeetCode-Go 题解：1209. Remove All Adjacent Duplicates in String II（k 倍重复项删除，栈计数法）
LeetCode-Go 题解1209. Remove All Adjacent Duplicates in String IIk 倍重复项删除栈计数法【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go本篇指南围绕 LeetCode 第 1209 题「Remove All Adjacent Duplicates in String II」展开结合 LeetCode-Go 仓库中的完整实现与测试用例讲解「k 倍重复项删除」问题的暴力解法与栈计数解法的原理、复杂度差异与 Go 代码细节。读完本文你将掌握如何用「栈 频次计数」在 O(n) 时间内解决这一类「相邻重复消除消消乐」问题并能直接复用仓库中可运行、可验证的 Go 源码。题目描述与约束给定一个字符串s一次k 倍重复项删除操作k duplicate removal指从s中选择k个相邻且相等的字母并删除它们使被删子串左侧和右侧的字符串重新拼接在一起。反复对s执行该操作直到无法继续删除为止返回最终字符串。题目保证最终答案唯一。约束条件如下1 s.length 10^52 k 10^4s仅包含小写英文字母示例分析示例 1Input: s abcd, k 2 Output: abcd字符串中不存在任何两个相邻且相等的字母无需删除。示例 2Input: s deeedbbcccbdaa, k 3 Output: aa删除过程分步如下先删除eee与ccc得到ddbbbdaa再删除bbb得到dddaa最后删除ddd得到aa。示例 3Input: s pbbcggttciiippooaais, k 2 Output: ps注意示例 3 中k 2这正是 1047. Remove All Adjacent Duplicates In String 的特殊情形每遇到两个相邻相同字符即消除。本题将其泛化到了任意k 2。解题思路一暴力扫描消消乐式反复消除最直观的做法是边读边消每追加一个字符就向前扫描统计以末尾字符结尾的连续相同字符个数一旦达到k个便整体切除。被切除后拼接形成的新字符串尾部可能再次出现k个相同字符因此需要循环检查直到尾部不再满足消除条件——这正是「消消乐」中碰撞即消除的过程。仓库中该解法对应 1209. Remove All Adjacent Duplicates in String II.go 中的removeDuplicates1// 解法二 暴力 func removeDuplicates1(s string, k int) string { arr, count, tmp : []rune{}, 0, # for _, v : range s { arr append(arr, v) for len(arr) 0 { count 0 tmp arr[len(arr)-1] for i : len(arr) - 1; i 0; i-- { if arr[i] ! tmp { break } count } if count k { arr arr[:len(arr)-k] } else { break } } } return string(arr) }该实现的核心机制使用[]rune切片模拟可变的字符串尾部逐个追加字符内层循环从末尾向前数出连续相同字符的个数count若count k执行arr arr[:len(arr)-k]切除末尾k个字符切除后继续回到内层循环开头重新统计新末尾的连续相同字符数直至不再满足消除条件才跳出。复杂度与瓶颈时间复杂度最坏情况下每次消除后都需要重新向前统计整体达到O(n²)空间复杂度O(n)用于存放拼接结果。低效的根源在于重复统计字符频次同一段连续相同字符可能被反复从后往前计数尤其是消除后又拼接出新的相同块时统计工作被一遍遍重做。解题思路二栈 频次计数O(n) 解法暴力解法的问题在于「每次都要重新数数」。如果每个字符的频次只统计一次就能把复杂度降下来。做法是使用一个栈每个栈元素存两个值字符本身以及该字符当前的连续出现频次。有了栈顶的频次信息就无需再向前回溯扫描每当栈顶字符与待入栈字符相同就只把栈顶频次加 1一旦栈顶频次达到k说明栈顶这一段刚好构成k个相邻且相等的字符直接弹出该元素即可。如此反复最终栈中剩下的就是所求字符串。栈解法 Go 实现仓库中的removeDuplicates即栈解法package leetcode // 解法一 stack func removeDuplicates(s string, k int) string { stack, arr : [][2]int{}, []byte{} for _, c : range s { i : int(c - a) if len(stack) 0 stack[len(stack)-1][0] i { stack[len(stack)-1][1] if stack[len(stack)-1][1] k { stack stack[:len(stack)-1] } } else { stack append(stack, [2]int{i, 1}) } } for _, pair : range stack { c : byte(pair[0] a) for i : 0; i pair[1]; i { arr append(arr, c) } } return string(arr) }逐步拆解这段代码栈结构stack的类型为[][2]int每个元素pair[0]存字符索引c - a即 025pair[1]存该字符当前的连续出现次数入栈逻辑新字符与栈顶字符不同或栈为空时压入[2]int{i, 1}频次从 1 开始计数与消除新字符与栈顶相同时仅stack[len(stack)-1][1]当频次累计到k说明栈顶已经形成k个相邻相同字符直接stack stack[:len(stack)-1]弹出整个元素。由于元素弹出后新的栈顶可能又是相同字符且此前频次已被记录过因此无需回溯天然支持连续消除如示例 2 中dddd依次消去一组ddd后剩下的d与后续字符的衔接重组结果扫描结束后遍历栈中剩余元素按pair[0] a还原字符并按pair[1]的频次展开拼入arr最终string(arr)即为答案。为什么它能做到 O(n)关键在于每个栈元素只入栈、出栈各一次字符一旦被压入栈其频次在栈顶时被原地累加达到k时整块弹出之后不会再被重新统计。相比暴力解法的反复向前计数这种「计数前置、消除后无需回溯」的设计将复杂度稳定在时间复杂度O(n)每个字符处理常数次空间复杂度O(n)栈最大深度为字符串长度。测试用例与验证仓库为本题配套了测试文件 1209. Remove All Adjacent Duplicates in String II_test.go采用本仓库统一的「问题描述结构体 参数/答案表」风格type para1209 struct { s string k int } type ans1209 struct { one string } func Test_Problem1209(t *testing.T) { qs : []question1209{ { para1209{deeedbbcccbdaa, 3}, ans1209{aa}, }, { para1209{pbbcggttciiippooaais, 2}, ans1209{ps}, }, } // ... }测试覆盖了题目给出的示例 2k 3与示例 3k 2并在循环中同时调用removeDuplicates与removeDuplicates1两种实现进行对比验证确保栈解法与暴力解法结果一致。若要运行整个仓库的全部测试可参照根目录的 gotest.shgo test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...其中-coverprofilecoverage.txt用于产出统一的覆盖率文件针对单个题目可在对应目录下执行go test -v -run Test_Problem1209与 1047 题的关联k 2 特例本题是 1047. Remove All Adjacent Duplicates In String 的推广1047 题固定删除 2 个相邻相同字符其实现1047. Remove All Adjacent Duplicates In String.go只用一个[]rune栈遇到与栈顶相同的字符即弹出func removeDuplicates1047(S string) string { stack : []rune{} for _, s : range S { if len(stack) 0 || len(stack) 0 stack[len(stack)-1] ! s { stack append(stack, s) } else { stack stack[:len(stack)-1] } } return string(stack) }对比可见1209 题的栈解法就是在 1047 题「字符栈」的基础上为每个栈元素附加了一个「频次」维度从而把「固定消 2 个」推广为「任意消 k 个」。理解了这一层演化关系就能把两题当作同一类「相邻重复消除」模型来记忆用栈保存字符与计数命中即消除消除后无需回溯。小结解法核心思想时间复杂度空间复杂度仓库实现暴力扫描追加字符后向前统计连续相同个数达到 k 即切除并循环检查O(n²)O(n)removeDuplicates1栈 频次栈元素存字符频次栈顶频次达 k 即弹出O(n)O(n)removeDuplicates面对s.length上限达 10⁵ 的输入规模O(n²) 的暴力解法存在超时风险栈计数法是本题的推荐实现一次扫描、计数前置、消除后免回溯既简洁又高效。该解法与 1047 题 一脉相承可作为面试中「相邻消除」类题目的通用模板直接套用。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考