---

1332. 删除回文子序列

• 标签：双指针、字符串
• 难度：简单

题目链接

• 1332. 删除回文子序列 - 力扣

题目大意

描述：给定一个字符串 $s$，每次操作可以删除 $s$ 的一个回文子序列（子序列不要求连续，但必须保持原顺序）。

要求：返回将字符串清空所需的最少操作次数。

说明：

• $0 \le s.length \le 1000$。
• $s$ 仅由小写字母 'a' 和 'b' 组成。

示例：

• 示例 1：

输入：s = "ababa"
输出：1
解释：字符串本身就是回文序列，只需要删除一次。

• 示例 2：

输入：s = "abb"
输出：2
解释："abb" -> "bb" -> "". 
先删除回文子序列 "a"，然后再删除 "bb"。

解题思路

思路 1：分类讨论

1. 核心思想

本题的关键在于发现两个重要性质：

1. 子序列不要求连续：意味着可以跳着选字符。
2. 字符串仅包含 'a' 和 'b'。

基于这两点，可以得出分类讨论的结论：

• 空字符串：$0$ 次。
• 本身是回文串：$1$ 次（直接删除整个字符串）。
• 不是回文串：最多 $2$ 次。第一次删除所有 'a'（它们构成一个回文子序列，因为全是相同字符），第二次删除所有 'b'。

2. 正确性证明

为什么非回文串最多 $2$ 次？

因为字符串只含 'a' 和 'b'$，所有 'a'组成的子序列是回文子序列（全相同字符），所有'b'组成的子序列也是回文子序列。所以最坏情况下，先删'a'再删'b'` 两步即可清空。

3. 举例说明

以 $s = "ababa"$ 为例：

• $s$ 本身就是回文串 → 直接删除，$1$ 次。

以 $s = "ab"$ 为例：

• $s$ 不是回文串。
• 第 1 次删除所有 'a' → 剩下 "b"。
• 第 2 次删除 "b" → 清空。
• 共 $2$ 次。

以 $s = "baab"$ 为例：

• $s$ 是回文串 → $1$ 次。

思路 1：代码

class Solution:
    def removePalindromeSub(self, s: str) -> int:
        if not s:
            return 0
        # 检查自身是否为回文串
        if s == s[::-1]:
            return 1
        return 2

思路 1：复杂度分析

• 时间复杂度：$O(n)$，检查回文串需要 $O(n)$ 时间。
• 空间复杂度：$O(1)$（反转字符串在 Python 中会创建新字符串，$O(n)$ 空间，但可以优化为双指针 $O(1)$）。

思路 1：双指针检查回文（空间优化）

class Solution:
    def removePalindromeSub(self, s: str) -> int:
        if not s:
            return 0
        # 双指针检查回文，O(1) 额外空间
        i, j = 0, len(s) - 1
        while i < j:
            if s[i] != s[j]:
                return 2
            i += 1
            j -= 1
        return 1

思路 1：复杂度分析（优化版）

• 时间复杂度：$O(n)$。
• 空间复杂度：$O(1)$，双指针避免字符串反转。

---

易错提醒

注意题目是回文子序列而不是回文子串。子序列可以不连续，这使得本题非常简单。如果是回文子串，则需要区间 DP 求解最少分割次数。