LeetCode 1750 最小删除字符数双指针 贪心解法剖析附 10 种语言实现【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode本文以 LeetCode 1750「删除字符串两端相同字符后的最短长度」Minimum Length of String After Deleting Similar Ends为核心讲解如何用「双指针 贪心」在 O(n) 时间内反复裁剪字符串两端相同字符并给出本仓库中 Python、Java、C、JavaScript、C#、Go、Kotlin、Swift、Rust 的完整可运行实现。读完你将掌握这类「两端相向处理 连续块收缩」问题的通用套路以及指针越界、单侧空删等易错点的规避方法。问题背景与核心目标给定一个仅由小写字母组成的字符串s你可以执行任意次如下操作同时删除一个非空前缀和一个非空后缀且要求被删除的前缀与后缀由相同的字符构成即前缀的所有字符相同、后缀的所有字符相同、且二者是同一个字符。问执行任意次操作后字符串可能达到的最短长度是多少。例如输入s ca首字符c与尾字符a不同无法执行任何删除答案就是2。输入s aabccabba两端都是a可以先删掉前缀aa与后缀a字符串变为bccab此时两端都是b再删掉前缀b与后缀b变为cc两端都是c但只剩 2 个字符时无法同时删除非空前缀与非空后缀会互相重叠最终最短长度为2。注意题目约束中的两个关键点前缀与后缀必须同时删除且各至少包含一个字符前缀内、后缀内各自是同一字符的连续块且前后缀是同一个字符允许重复执行直到无法再操作为止求最终剩余串的最小长度可以为 0。前置知识在阅读解法前建议先熟悉以下三个基础技能本仓库的 两数之和 II双指针、盛最多水的容器贪心 双指针 等文章也可作为配套练习双指针技术Two Pointers在数组/字符串两端各放置一个指针相向移动处理元素常能将暴力 O(n²) 降为 O(n)。贪心算法Greedy Algorithms每步做出当前看起来最优的局部选择并证明它能导向全局最优解。字符串操作String Manipulation字符比较、子串/连续块的遍历与裁剪。解法Greedy Two Pointers直觉Intuition我们可以反复从字符串两端修剪匹配的字符。每次操作要求前缀与后缀由相同字符构成且两端各至少删除一个字符。使用两个指针分别从首尾出发判断s[l] s[r]若相等说明这一轮可以操作就贪心地把该字符在两端的全部连续出现一次删光若不相等说明没有任何可执行的删除立即停止。为什么贪心是安全的因为现在多删只会对后续操作有帮助或至少不造成伤害当前字符块是免费的删除资源先删掉它不会改变中间剩余部分两端字符的相对关系而少删则可能白白浪费一次把字符串变短的机会。因此一次性删除两端该字符的所有连续出现能保证得到最短剩余长度。算法Algorithm初始化两个指针l指向字符串开头0r指向字符串结尾len(s) - 1。当l r且s[l] s[r]时循环记录当前匹配的字符记为tmpl向右跳过所有连续的tmp含当前指向的字符r向左跳过所有连续的tmp含当前指向的字符。循环结束后剩余部分的长度为r - l 1即为答案。若指针发生交叉l r说明整个字符串都被删光了返回0。这里有一个实现细节值得注意内层两个 while 的条件都要写成l r而不是l r。因为当剩余部分全部由同一个字符组成时例如aaaa两端指针会一路相向扫过l可能越过r用l r既能保证不访问越界下标也能让最终结果自然落在r - l 1 0。多语言实现以下是本仓库 articles/minimum-length-of-string-after-deleting-similar-ends.md 中给出的完整实现与仓库内 python/1750-minimum-length-of-string-after-deleting-similar-ends.py 和 java/1750-minimum-length-of-string-after-deleting-similar-ends.java 中的实际提交代码保持一致。Pythonclass Solution: def minimumLength(self, s: str) - int: l, r 0, len(s) - 1 while l r and s[l] s[r]: tmp s[l] while l r and s[l] tmp: l 1 while l r and s[r] tmp: r - 1 return r - l 1Javapublic class Solution { public int minimumLength(String s) { int l 0, r s.length() - 1; while (l r s.charAt(l) s.charAt(r)) { char tmp s.charAt(l); while (l r s.charAt(l) tmp) { l; } while (l r s.charAt(r) tmp) { r--; } } return r - l 1; } }Cclass Solution { public: int minimumLength(string s) { int l 0, r s.length() - 1; while (l r s[l] s[r]) { char tmp s[l]; while (l r s[l] tmp) { l; } while (l r s[r] tmp) { r--; } } return r - l 1; } };JavaScriptclass Solution { /** * param {string} s * return {number} */ minimumLength(s) { let l 0, r s.length - 1; while (l r s[l] s[r]) { const tmp s[l]; while (l r s[l] tmp) { l; } while (l r s[r] tmp) { r--; } } return r - l 1; } }C#public class Solution { public int MinimumLength(string s) { int l 0, r s.Length - 1; while (l r s[l] s[r]) { char tmp s[l]; while (l r s[l] tmp) { l; } while (l r s[r] tmp) { r--; } } return r - l 1; } }Gofunc minimumLength(s string) int { l, r : 0, len(s)-1 for l r s[l] s[r] { tmp : s[l] for l r s[l] tmp { l } for l r s[r] tmp { r-- } } return r - l 1 }Kotlinclass Solution { fun minimumLength(s: String): Int { var l 0 var r s.length - 1 while (l r s[l] s[r]) { val tmp s[l] while (l r s[l] tmp) { l } while (l r s[r] tmp) { r-- } } return r - l 1 } }Swiftclass Solution { func minimumLength(_ s: String) - Int { let chars Array(s) var l 0 var r chars.count - 1 while l r chars[l] chars[r] { let tmp chars[l] while l r chars[l] tmp { l 1 } while l r chars[r] tmp { r - 1 } } return r - l 1 } }Rustimpl Solution { pub fn minimum_length(s: String) - i32 { let s s.as_bytes(); let (mut l, mut r) (0i32, s.len() as i32 - 1); while l r s[l as usize] s[r as usize] { let tmp s[l as usize]; while l r s[l as usize] tmp { l 1; } while l r s[r as usize] tmp { r - 1; } } r - l 1 } }手动推演示例以s aabccabba为例跟踪指针变化轮次当前字符串逻辑剩余部分两端字符操作lr初始aabccabbaaa删前缀aa、后缀a271bccabbb删前缀b、后缀b362cccc但l1 r-1无法同时删除非空前缀与非空后缀停止36最终r - l 1 4这里需要修正第二轮循环开始前l2, r7s[2]b, s[7]b相等进入循环后tmpbl右移跳过s[2]下标 2 是b下标 3 是c停止→l3r左移跳过s[7]下标 7 是b下标 6 是a停止→r6。此时l3 r6且s[3]c ! s[6]a外层循环结束答案为6 - 3 1 4。若输入为aaaal0, r3进入循环后l一路扫到 4、r一路扫到 -1内层l r保护避免越界最终r - l 1 -1 - 4 1 -4不对——这里要再次强调由于r与l的移动都受l r约束指针会在交叉的瞬间停下l扫到 4 时因l r不成立此时r已变为 -1——实际执行顺序是l从 0 扫到 4s[4]越界前停下因为l4时l r中r已更新。两个内层循环交错推进最终停在l4, r-1r - l 1 -4显然不对。实际上正确的结果是 0。让我们严格模拟l0, r3外层进入s[0]as[3]。tmpa。第一个内层循环l003且s[0]a→l113且s[1]a→l223且s[2]a→l333且s[3]a→l443不成立退出。第二个内层循环r343不成立直接退出r保持 3。此时l4, r3外层条件l r4 3为假循环结束。r - l 1 3 - 4 1 0。✅ 结果为 0。再验证s a单字符l0, r0外层l r不成立直接返回0 - 0 1 1。✅ 单字符无法操作长度为 1。时间复杂度与空间复杂度时间复杂度O(n)。l与r各自最多遍历字符串一遍内层循环整体分摊后每个字符最多被访问常数次整体线性。空间复杂度O(1)额外空间。除两个指针和一个临时字符变量外不使用额外数据结构。注意 Rust 与 Swift 实现中为了安全访问将字符串转为字节数组 / 字符数组这属于语言层面的必要转换Swift 的String索引不是 O(1) 随机访问转换本身占用 O(n) 临时空间但算法逻辑本身不依赖额外存储。常见陷阱Common Pitfalls陷阱一指针越过边界而未加保护当剩余部分全部由同一个字符组成时如aaaa内层循环中两个指针会相向穿越对方。内层 while 必须使用l r条件若写成l rl可能一路越过r继续访问在 Python/Java 中会造成下标越界异常在 C/C/Rust 中是未定义行为或 panicl r保证在指针交叉前停止使最终r - l 1恰好为 0不会产生负数长度。陷阱二允许单侧为空题目要求删除的是非空前缀 非空后缀两侧各至少一个字符。常见错误是当s[l] s[r]但l与r相邻例如aa时仍尝试各删一个导致两侧删除区间重叠。本解法通过外层l r条件天然规避当剩余串长度小于 2 时循环不再进入从而保证每次操作两侧都非空且互不重叠。陷阱三忘记两端必须为同一字符的整体性循环条件是l r s[l] s[r]只要任一端字符改变或两端字符不同就必须立即停止。不能只比较其中一端也不能在字符不同时继续尝试删除。与本仓库其他双指针题目的联系本题是两端相向双指针的典型代表与本仓库中以下题目共享同一思维框架两数之和 II有序数组同样首尾指针相向移动根据比较结果决定移动哪一端盛最多水的容器贪心 首尾指针每步移动较矮一侧验证回文串首尾指针逐字符比较本题在此基础上增加了连续块整体跳过的操作移动零 与 原地移除元素单侧双指针的变体可作为双指针体系的对照练习。完整的双指针类别题目清单可参见 README.md 中的 Two Pointers 章节。仓库内对应题解分布在 python/1750-minimum-length-of-string-after-deleting-similar-ends.py 与 java/1750-minimum-length-of-string-after-deleting-similar-ends.java可按需对照阅读。小结问题本质反复删除两端相同字符的连续块求最短剩余长度解法核心双指针 贪心一次性删光两端该字符的全部连续出现复杂度时间 O(n)空间 O(1)易错点内层循环用l r防越界外层用l r保证两侧删除都非空。掌握了这一套路你不仅能秒杀本题还能在面对两端同时收缩类的字符串/数组问题时快速定位到双指针 贪心的解法框架。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 LeetCode 1750 最小删除字符数：双指针 + 贪心解法剖析（附 10 种语言实现）
LeetCode 1750 最小删除字符数双指针 贪心解法剖析附 10 种语言实现【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode本文以 LeetCode 1750「删除字符串两端相同字符后的最短长度」Minimum Length of String After Deleting Similar Ends为核心讲解如何用「双指针 贪心」在 O(n) 时间内反复裁剪字符串两端相同字符并给出本仓库中 Python、Java、C、JavaScript、C#、Go、Kotlin、Swift、Rust 的完整可运行实现。读完你将掌握这类「两端相向处理 连续块收缩」问题的通用套路以及指针越界、单侧空删等易错点的规避方法。问题背景与核心目标给定一个仅由小写字母组成的字符串s你可以执行任意次如下操作同时删除一个非空前缀和一个非空后缀且要求被删除的前缀与后缀由相同的字符构成即前缀的所有字符相同、后缀的所有字符相同、且二者是同一个字符。问执行任意次操作后字符串可能达到的最短长度是多少。例如输入s ca首字符c与尾字符a不同无法执行任何删除答案就是2。输入s aabccabba两端都是a可以先删掉前缀aa与后缀a字符串变为bccab此时两端都是b再删掉前缀b与后缀b变为cc两端都是c但只剩 2 个字符时无法同时删除非空前缀与非空后缀会互相重叠最终最短长度为2。注意题目约束中的两个关键点前缀与后缀必须同时删除且各至少包含一个字符前缀内、后缀内各自是同一字符的连续块且前后缀是同一个字符允许重复执行直到无法再操作为止求最终剩余串的最小长度可以为 0。前置知识在阅读解法前建议先熟悉以下三个基础技能本仓库的 两数之和 II双指针、盛最多水的容器贪心 双指针 等文章也可作为配套练习双指针技术Two Pointers在数组/字符串两端各放置一个指针相向移动处理元素常能将暴力 O(n²) 降为 O(n)。贪心算法Greedy Algorithms每步做出当前看起来最优的局部选择并证明它能导向全局最优解。字符串操作String Manipulation字符比较、子串/连续块的遍历与裁剪。解法Greedy Two Pointers直觉Intuition我们可以反复从字符串两端修剪匹配的字符。每次操作要求前缀与后缀由相同字符构成且两端各至少删除一个字符。使用两个指针分别从首尾出发判断s[l] s[r]若相等说明这一轮可以操作就贪心地把该字符在两端的全部连续出现一次删光若不相等说明没有任何可执行的删除立即停止。为什么贪心是安全的因为现在多删只会对后续操作有帮助或至少不造成伤害当前字符块是免费的删除资源先删掉它不会改变中间剩余部分两端字符的相对关系而少删则可能白白浪费一次把字符串变短的机会。因此一次性删除两端该字符的所有连续出现能保证得到最短剩余长度。算法Algorithm初始化两个指针l指向字符串开头0r指向字符串结尾len(s) - 1。当l r且s[l] s[r]时循环记录当前匹配的字符记为tmpl向右跳过所有连续的tmp含当前指向的字符r向左跳过所有连续的tmp含当前指向的字符。循环结束后剩余部分的长度为r - l 1即为答案。若指针发生交叉l r说明整个字符串都被删光了返回0。这里有一个实现细节值得注意内层两个 while 的条件都要写成l r而不是l r。因为当剩余部分全部由同一个字符组成时例如aaaa两端指针会一路相向扫过l可能越过r用l r既能保证不访问越界下标也能让最终结果自然落在r - l 1 0。多语言实现以下是本仓库 articles/minimum-length-of-string-after-deleting-similar-ends.md 中给出的完整实现与仓库内 python/1750-minimum-length-of-string-after-deleting-similar-ends.py 和 java/1750-minimum-length-of-string-after-deleting-similar-ends.java 中的实际提交代码保持一致。Pythonclass Solution: def minimumLength(self, s: str) - int: l, r 0, len(s) - 1 while l r and s[l] s[r]: tmp s[l] while l r and s[l] tmp: l 1 while l r and s[r] tmp: r - 1 return r - l 1Javapublic class Solution { public int minimumLength(String s) { int l 0, r s.length() - 1; while (l r s.charAt(l) s.charAt(r)) { char tmp s.charAt(l); while (l r s.charAt(l) tmp) { l; } while (l r s.charAt(r) tmp) { r--; } } return r - l 1; } }Cclass Solution { public: int minimumLength(string s) { int l 0, r s.length() - 1; while (l r s[l] s[r]) { char tmp s[l]; while (l r s[l] tmp) { l; } while (l r s[r] tmp) { r--; } } return r - l 1; } };JavaScriptclass Solution { /** * param {string} s * return {number} */ minimumLength(s) { let l 0, r s.length - 1; while (l r s[l] s[r]) { const tmp s[l]; while (l r s[l] tmp) { l; } while (l r s[r] tmp) { r--; } } return r - l 1; } }C#public class Solution { public int MinimumLength(string s) { int l 0, r s.Length - 1; while (l r s[l] s[r]) { char tmp s[l]; while (l r s[l] tmp) { l; } while (l r s[r] tmp) { r--; } } return r - l 1; } }Gofunc minimumLength(s string) int { l, r : 0, len(s)-1 for l r s[l] s[r] { tmp : s[l] for l r s[l] tmp { l } for l r s[r] tmp { r-- } } return r - l 1 }Kotlinclass Solution { fun minimumLength(s: String): Int { var l 0 var r s.length - 1 while (l r s[l] s[r]) { val tmp s[l] while (l r s[l] tmp) { l } while (l r s[r] tmp) { r-- } } return r - l 1 } }Swiftclass Solution { func minimumLength(_ s: String) - Int { let chars Array(s) var l 0 var r chars.count - 1 while l r chars[l] chars[r] { let tmp chars[l] while l r chars[l] tmp { l 1 } while l r chars[r] tmp { r - 1 } } return r - l 1 } }Rustimpl Solution { pub fn minimum_length(s: String) - i32 { let s s.as_bytes(); let (mut l, mut r) (0i32, s.len() as i32 - 1); while l r s[l as usize] s[r as usize] { let tmp s[l as usize]; while l r s[l as usize] tmp { l 1; } while l r s[r as usize] tmp { r - 1; } } r - l 1 } }手动推演示例以s aabccabba为例跟踪指针变化轮次当前字符串逻辑剩余部分两端字符操作lr初始aabccabbaaa删前缀aa、后缀a271bccabbb删前缀b、后缀b362cccc但l1 r-1无法同时删除非空前缀与非空后缀停止36最终r - l 1 4这里需要修正第二轮循环开始前l2, r7s[2]b, s[7]b相等进入循环后tmpbl右移跳过s[2]下标 2 是b下标 3 是c停止→l3r左移跳过s[7]下标 7 是b下标 6 是a停止→r6。此时l3 r6且s[3]c ! s[6]a外层循环结束答案为6 - 3 1 4。若输入为aaaal0, r3进入循环后l一路扫到 4、r一路扫到 -1内层l r保护避免越界最终r - l 1 -1 - 4 1 -4不对——这里要再次强调由于r与l的移动都受l r约束指针会在交叉的瞬间停下l扫到 4 时因l r不成立此时r已变为 -1——实际执行顺序是l从 0 扫到 4s[4]越界前停下因为l4时l r中r已更新。两个内层循环交错推进最终停在l4, r-1r - l 1 -4显然不对。实际上正确的结果是 0。让我们严格模拟l0, r3外层进入s[0]as[3]。tmpa。第一个内层循环l003且s[0]a→l113且s[1]a→l223且s[2]a→l333且s[3]a→l443不成立退出。第二个内层循环r343不成立直接退出r保持 3。此时l4, r3外层条件l r4 3为假循环结束。r - l 1 3 - 4 1 0。✅ 结果为 0。再验证s a单字符l0, r0外层l r不成立直接返回0 - 0 1 1。✅ 单字符无法操作长度为 1。时间复杂度与空间复杂度时间复杂度O(n)。l与r各自最多遍历字符串一遍内层循环整体分摊后每个字符最多被访问常数次整体线性。空间复杂度O(1)额外空间。除两个指针和一个临时字符变量外不使用额外数据结构。注意 Rust 与 Swift 实现中为了安全访问将字符串转为字节数组 / 字符数组这属于语言层面的必要转换Swift 的String索引不是 O(1) 随机访问转换本身占用 O(n) 临时空间但算法逻辑本身不依赖额外存储。常见陷阱Common Pitfalls陷阱一指针越过边界而未加保护当剩余部分全部由同一个字符组成时如aaaa内层循环中两个指针会相向穿越对方。内层 while 必须使用l r条件若写成l rl可能一路越过r继续访问在 Python/Java 中会造成下标越界异常在 C/C/Rust 中是未定义行为或 panicl r保证在指针交叉前停止使最终r - l 1恰好为 0不会产生负数长度。陷阱二允许单侧为空题目要求删除的是非空前缀 非空后缀两侧各至少一个字符。常见错误是当s[l] s[r]但l与r相邻例如aa时仍尝试各删一个导致两侧删除区间重叠。本解法通过外层l r条件天然规避当剩余串长度小于 2 时循环不再进入从而保证每次操作两侧都非空且互不重叠。陷阱三忘记两端必须为同一字符的整体性循环条件是l r s[l] s[r]只要任一端字符改变或两端字符不同就必须立即停止。不能只比较其中一端也不能在字符不同时继续尝试删除。与本仓库其他双指针题目的联系本题是两端相向双指针的典型代表与本仓库中以下题目共享同一思维框架两数之和 II有序数组同样首尾指针相向移动根据比较结果决定移动哪一端盛最多水的容器贪心 首尾指针每步移动较矮一侧验证回文串首尾指针逐字符比较本题在此基础上增加了连续块整体跳过的操作移动零 与 原地移除元素单侧双指针的变体可作为双指针体系的对照练习。完整的双指针类别题目清单可参见 README.md 中的 Two Pointers 章节。仓库内对应题解分布在 python/1750-minimum-length-of-string-after-deleting-similar-ends.py 与 java/1750-minimum-length-of-string-after-deleting-similar-ends.java可按需对照阅读。小结问题本质反复删除两端相同字符的连续块求最短剩余长度解法核心双指针 贪心一次性删光两端该字符的全部连续出现复杂度时间 O(n)空间 O(1)易错点内层循环用l r防越界外层用l r保证两侧删除都非空。掌握了这一套路你不仅能秒杀本题还能在面对两端同时收缩类的字符串/数组问题时快速定位到双指针 贪心的解法框架。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考