LeetCode 1332. 删除回文子序列remove-palindromic-subsequences题解利用双字符约束将问题化归为三次判断【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode本文是 leetcode 题解仓库记录自己的 LeetCode 解题之路中 1332. 删除回文子序列 一题的完整技术剖析。该题被收录于仓库的 简单难度题目合集 与 README 题解索引 中是一道典型的“反直觉”签到题表面上是删除与回文的组合问题实际只要抓住“字符串仅由 a 和 b 构成”这一约束就能把答案压缩到 0、1、2 三种取值。读完本文你将掌握子序列与子串的本质区别、回文判定的双指针模板以及“先删全部 a 再删全部 b”这一构造性证明并能独立完成 Python3 与 Java 两种语言的实现。题目描述与核心约束给你一个字符串 s它仅由字母 a 和 b 组成。每一次删除操作都可以从 s 中删除一个回文子序列。返回删除给定字符串中所有字符字符串为空的最小删除次数。题目给出的两个定义是破题关键子序列可以通过删除原字符串某些字符、而不改变原字符顺序得到的字符串。注意它不要求连续这是与“子串”最大的不同。回文向后读和向前读一致的字符串。输入输出示例输入输出说明s ababa1字符串本身就是回文序列一次删除即可s abb2abb→ 删除回文子序列a→bb→ 删除bb→s baabb2baabb→ 删除回文子序列baab→b→ 删除b→s 0空字符串无需删除提示与数据范围0 s.length 1000s仅包含字母a和b从数据范围看即便用最朴素的 O(N²) 暴力也能通过但本题的真正考点在于找到常数级别的答案而不是写一个复杂的模拟。前置知识回文Palindrome正读反读相同。本题的删除对象是“回文子序列”而不是“回文子串”理解二者的差异是拿到最优解的前提。双指针用于 O(N) 时间判断整个字符串是否为回文具体模板可参考仓库中 125. 验证回文串 的解法。思路分析为什么答案最多只有 2原题解一针见血地指出这是一道“抖机灵”的题目同类题目还有 1297. 子串的最大出现次数同样是靠题目隐藏条件大幅简化问题。最多 2 次的构造性证明由于字符串只由a和b两种字符构成而由同一种字符组成的任意子序列必然是回文aaaa…a正读反读完全一致bbbb…b同理。因此可以这样构造删除方案第一次删除删除 s 中所有的a它们组成一个由a构成的回文子序列此时剩下的字符串全部由b组成第二次删除删除剩余所有的b同样是一个回文子序列字符串变为空。所以无论 s 有多长、多么“乱序”最多只需要 2 次就能清空全部字符。这正是“删除子序列”而非“删除子串”带来的自由度——我们可以隔空取字符不受连续性限制。何时是 0 次或 1 次0 次字符串本身为空s.length 0这是最容易遗漏的边界情况。1 次整个字符串 s 本身就是回文。因为一次删除就清空所有字符意味着被删除的“那个子序列”恰好覆盖了全部字符即 s 自身必须是回文。示例ababa正属此类。2 次s 非空且不是回文。此时不可能 1 次完成而由上面的构造可知 2 次一定足够因此答案就是 2。关键点解析原题解特别强调一定要利用题目条件“只含有 a 和 b 两个字符”。如果忽视这一条件、试图去模拟“每次找最长回文子序列并删除”的贪心或 DP 过程就会把一道 O(N) 的签到题做成 NP 级别的困难题。识别“题目给的额外约束是否能把问题化简到常数复杂度”是这类抖机灵题的核心套路。回文判定双指针夹逼判断 s 是否为回文用头尾两个指针向中间夹逼即可两指针指向的字符不同则直接判否相同则同时向中间移动直到两指针相遇。该思路的完整推导与图示见仓库中 125. 验证回文串 的解法其时间复杂度为 O(N)。本题在此基础上只需再套一层“空串判 0、回文判 1、否则判 2”的外壳。对比516. 最长回文子序列本题容易与仓库中另一道经典题 516. 最长回文子序列 混淆。516 求的是“最长回文子序列的长度”需要在任意字符集上做区间 DP而 1332 删除的是“任意回文子序列”且字符集被限定为只有 a、b 两种因此退化成了一次回文判定。二者对照学习能更清楚地体会“字符集规模”对题目难度的影响。代码实现原题解给出 Python3 与 Java 两种实现。代码支持Python3、Java。Python3双指针版如果你希望把回文判定写清楚、便于面试时讲解思路可以使用双指针版本class Solution: def removePalindromeSub(self, s: str) - int: if s : return 0 def isPalindrome(s): l 0 r len(s) - 1 while l r: if s[l] ! s[r]: return False l 1 r - 1 return True return 1 if isPalindrome(s) else 2Python3切片简写版如果认为回文判定不是本题重点可以用 Python 的字符串切片一步完成语义完全相同class Solution: def removePalindromeSub(self, s: str) - int: if s : return 0 return 1 if s s[::-1] else 2Java 实现Java 侧利用StringBuilder.reverse()构造逆序串进行比较class Solution { public int removePalindromeSub(String s) { if (.equals(s)) { return 0; } if (s.equals(new StringBuilder(s).reverse().toString())) { return 1; } return 2; } }复杂度分析时间复杂度O(N)其中 N 为字符串长度。双指针版仅需一趟线性扫描切片版与reverse()版也只需线性时间构造逆序串。空间复杂度双指针版为 O(1)切片版 /reverse()版需要额外构造一份逆序字符串为 O(N)。若对常数空间有要求面试时优先给出双指针实现。归纳与延伸读题先找隐藏约束看到“仅由 a、b 组成”就应意识到答案的取值空间被大幅压缩本题答案 ∈ {0, 1, 2}边界先行空串对应 0是本题唯一的多分支入口遗漏即错子序列 ≠ 子串正是“可跳着删”的子序列定义才让“一次删光所有 a、一次删光所有 b”的两次方案成为可能与回文类题串联复习可把 125. 验证回文串判回文、516. 最长回文子序列DP 求长度与本串起来对比形成回文题型的完整知识链。该题连同其余简单题解一起收录于仓库 简单难度题目合集并在 README 总索引 中列出适合作为刷题路径中“识别题目套路”的训练样本。【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
LeetCode 1332. 删除回文子序列（remove-palindromic-subsequences）题解：利用双字符约束将问题化归为三次判断
LeetCode 1332. 删除回文子序列remove-palindromic-subsequences题解利用双字符约束将问题化归为三次判断【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode本文是 leetcode 题解仓库记录自己的 LeetCode 解题之路中 1332. 删除回文子序列 一题的完整技术剖析。该题被收录于仓库的 简单难度题目合集 与 README 题解索引 中是一道典型的“反直觉”签到题表面上是删除与回文的组合问题实际只要抓住“字符串仅由 a 和 b 构成”这一约束就能把答案压缩到 0、1、2 三种取值。读完本文你将掌握子序列与子串的本质区别、回文判定的双指针模板以及“先删全部 a 再删全部 b”这一构造性证明并能独立完成 Python3 与 Java 两种语言的实现。题目描述与核心约束给你一个字符串 s它仅由字母 a 和 b 组成。每一次删除操作都可以从 s 中删除一个回文子序列。返回删除给定字符串中所有字符字符串为空的最小删除次数。题目给出的两个定义是破题关键子序列可以通过删除原字符串某些字符、而不改变原字符顺序得到的字符串。注意它不要求连续这是与“子串”最大的不同。回文向后读和向前读一致的字符串。输入输出示例输入输出说明s ababa1字符串本身就是回文序列一次删除即可s abb2abb→ 删除回文子序列a→bb→ 删除bb→s baabb2baabb→ 删除回文子序列baab→b→ 删除b→s 0空字符串无需删除提示与数据范围0 s.length 1000s仅包含字母a和b从数据范围看即便用最朴素的 O(N²) 暴力也能通过但本题的真正考点在于找到常数级别的答案而不是写一个复杂的模拟。前置知识回文Palindrome正读反读相同。本题的删除对象是“回文子序列”而不是“回文子串”理解二者的差异是拿到最优解的前提。双指针用于 O(N) 时间判断整个字符串是否为回文具体模板可参考仓库中 125. 验证回文串 的解法。思路分析为什么答案最多只有 2原题解一针见血地指出这是一道“抖机灵”的题目同类题目还有 1297. 子串的最大出现次数同样是靠题目隐藏条件大幅简化问题。最多 2 次的构造性证明由于字符串只由a和b两种字符构成而由同一种字符组成的任意子序列必然是回文aaaa…a正读反读完全一致bbbb…b同理。因此可以这样构造删除方案第一次删除删除 s 中所有的a它们组成一个由a构成的回文子序列此时剩下的字符串全部由b组成第二次删除删除剩余所有的b同样是一个回文子序列字符串变为空。所以无论 s 有多长、多么“乱序”最多只需要 2 次就能清空全部字符。这正是“删除子序列”而非“删除子串”带来的自由度——我们可以隔空取字符不受连续性限制。何时是 0 次或 1 次0 次字符串本身为空s.length 0这是最容易遗漏的边界情况。1 次整个字符串 s 本身就是回文。因为一次删除就清空所有字符意味着被删除的“那个子序列”恰好覆盖了全部字符即 s 自身必须是回文。示例ababa正属此类。2 次s 非空且不是回文。此时不可能 1 次完成而由上面的构造可知 2 次一定足够因此答案就是 2。关键点解析原题解特别强调一定要利用题目条件“只含有 a 和 b 两个字符”。如果忽视这一条件、试图去模拟“每次找最长回文子序列并删除”的贪心或 DP 过程就会把一道 O(N) 的签到题做成 NP 级别的困难题。识别“题目给的额外约束是否能把问题化简到常数复杂度”是这类抖机灵题的核心套路。回文判定双指针夹逼判断 s 是否为回文用头尾两个指针向中间夹逼即可两指针指向的字符不同则直接判否相同则同时向中间移动直到两指针相遇。该思路的完整推导与图示见仓库中 125. 验证回文串 的解法其时间复杂度为 O(N)。本题在此基础上只需再套一层“空串判 0、回文判 1、否则判 2”的外壳。对比516. 最长回文子序列本题容易与仓库中另一道经典题 516. 最长回文子序列 混淆。516 求的是“最长回文子序列的长度”需要在任意字符集上做区间 DP而 1332 删除的是“任意回文子序列”且字符集被限定为只有 a、b 两种因此退化成了一次回文判定。二者对照学习能更清楚地体会“字符集规模”对题目难度的影响。代码实现原题解给出 Python3 与 Java 两种实现。代码支持Python3、Java。Python3双指针版如果你希望把回文判定写清楚、便于面试时讲解思路可以使用双指针版本class Solution: def removePalindromeSub(self, s: str) - int: if s : return 0 def isPalindrome(s): l 0 r len(s) - 1 while l r: if s[l] ! s[r]: return False l 1 r - 1 return True return 1 if isPalindrome(s) else 2Python3切片简写版如果认为回文判定不是本题重点可以用 Python 的字符串切片一步完成语义完全相同class Solution: def removePalindromeSub(self, s: str) - int: if s : return 0 return 1 if s s[::-1] else 2Java 实现Java 侧利用StringBuilder.reverse()构造逆序串进行比较class Solution { public int removePalindromeSub(String s) { if (.equals(s)) { return 0; } if (s.equals(new StringBuilder(s).reverse().toString())) { return 1; } return 2; } }复杂度分析时间复杂度O(N)其中 N 为字符串长度。双指针版仅需一趟线性扫描切片版与reverse()版也只需线性时间构造逆序串。空间复杂度双指针版为 O(1)切片版 /reverse()版需要额外构造一份逆序字符串为 O(N)。若对常数空间有要求面试时优先给出双指针实现。归纳与延伸读题先找隐藏约束看到“仅由 a、b 组成”就应意识到答案的取值空间被大幅压缩本题答案 ∈ {0, 1, 2}边界先行空串对应 0是本题唯一的多分支入口遗漏即错子序列 ≠ 子串正是“可跳着删”的子序列定义才让“一次删光所有 a、一次删光所有 b”的两次方案成为可能与回文类题串联复习可把 125. 验证回文串判回文、516. 最长回文子序列DP 求长度与本串起来对比形成回文题型的完整知识链。该题连同其余简单题解一起收录于仓库 简单难度题目合集并在 README 总索引 中列出适合作为刷题路径中“识别题目套路”的训练样本。【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考