1332. 删除回文子序列

https://leetcode-cn.com/problems/remove-palindromic-subsequences/

题目描述

给你一个字符串 s，它仅由字母 'a' 和 'b' 组成。每一次删除操作都可以从 s 中删除一个回文 子序列。

返回删除给定字符串中所有字符（字符串为空）的最小删除次数。

「子序列」定义：如果一个字符串可以通过删除原字符串某些字符而不改变原字符顺序得到，那么这个字符串就是原字符串的一个子序列。

「回文」定义：如果一个字符串向后和向前读是一致的，那么这个字符串就是一个回文。

 

示例 1：

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

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

输入：s = "baabb"
输出：2
解释："baabb" -> "b" -> "".
先删除回文子序列 "baab"，然后再删除 "b"。
示例 4：

输入：s = ""
输出：0
 

提示：

0 <= s.length <= 1000
s 仅包含字母 'a'  和 'b'
在真实的面试中遇到过这道题？

前置知识

• 回文

公司

• 暂无

思路

这又是一道“抖机灵”的题目，类似的题目有1297.maximum-number-of-occurrences-of-a-substring

由于只有 a 和 b 两个字符。其实最多的消除次数就是 2。这是因为每次我们可以消除一个子序列，而不是消除一个子串。这样我们就可以可以先消除全部的 1 再消除全部的 2（先消除 2 也一样），这样只需要两次即可完成。 有可能 0 次或者 1 次么？有的。

比如题目给的一次消除的情况，题目给的例子是“ababa”，我们发现其实它本身就是一个回文串，所以才可以一次全部消除。那么思路就有了：

• 如果 s 是回文，则我们需要一次消除

• 否则需要两次

• 一定要注意特殊情况， 对于空字符串，我们需要 0 次

判读回文的话只需要两个指针夹逼即可，具体思路可参考125. 验证回文串

关键点解析

• 注意审题目，一定要利用题目条件“只含有 a 和 b 两个字符”否则容易做的很麻烦

代码

代码支持：Python3、Java

Python3 Code:

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 2

如果你觉得判断回文不是本题重点，也可以简单实现：

Python3 Code:

class Solution:
    def removePalindromeSub(self, s: str) -> int:
        if s == '':
            return 0
        return 1 if s == s[::-1] else 2

Java Code：

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)$

• 空间复杂度：$O(1)$

更多题解可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 37K star 啦。

关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。