原文链接: https://leetcode-cn.com/problems/remove-palindromic-subsequences
英文原文
You are given a string s consisting only of letters 'a' and 'b'. In a single step you can remove one palindromic subsequence from s.
Return the minimum number of steps to make the given string empty.
A string is a subsequence of a given string if it is generated by deleting some characters of a given string without changing its order. Note that a subsequence does not necessarily need to be contiguous.
A string is called palindrome if is one that reads the same backward as well as forward.
Example 1:
Input: s = "ababa" Output: 1 Explanation: s is already a palindrome, so its entirety can be removed in a single step.
Example 2:
Input: s = "abb" Output: 2 Explanation: "abb" -> "bb" -> "". Remove palindromic subsequence "a" then "bb".
Example 3:
Input: s = "baabb" Output: 2 Explanation: "baabb" -> "b" -> "". Remove palindromic subsequence "baab" then "b".
Constraints:
1 <= s.length <= 1000s[i]is either'a'or'b'.
中文题目
给你一个字符串 s，它仅由字母 'a' 和 'b' 组成。每一次删除操作都可以从 s 中删除一个回文 子序列。
返回删除给定字符串中所有字符（字符串为空）的最小删除次数。
「子序列」定义：如果一个字符串可以通过删除原字符串某些字符而不改变原字符顺序得到，那么这个字符串就是原字符串的一个子序列。
「回文」定义：如果一个字符串向后和向前读是一致的，那么这个字符串就是一个回文。
示例 1：
输入：s = "ababa" 输出：1 解释：字符串本身就是回文序列，只需要删除一次。
示例 2：
输入：s = "abb" 输出：2 解释："abb" -> "bb" -> "". 先删除回文子序列 "a"，然后再删除 "bb"。
示例 3：
输入：s = "baabb" 输出：2 解释："baabb" -> "b" -> "". 先删除回文子序列 "baab"，然后再删除 "b"。
提示：
1 <= s.length <= 1000s仅包含字母'a'和'b'
通过代码
高赞题解
1332. 删除回文子序列
Hi 大家好，我是张小猪。欢迎来到『宝宝也能看懂』系列之 leetcode 周赛题解。
这里是第 173 期的第 1 题，也是题目列表中的第 1332 题 – 『删除回文子序列』
题目描述
给你一个字符串 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 <= 1000s仅包含字母 ‘a’ 和 ‘b’
官方难度
EASY
解决思路
题目的意思非常的简单，给定一个只由 ‘a’ 和 ‘b’ 这两种字母组成的字符串，需要返回把该字符串删空所需的最小次数。要求也只有一条，是每次删除的是一个回文子序列。
等等，what？excuse me？黑人问号脸…又是回文字符串，又是最小次数，还是 EASY 难度…吓得小猪赶紧揉了揉眼睛，在确认没看错之后赶紧吃了一袋薯片压压惊…
想了想，发现没有借口再吃第二袋薯片了，于是决定还是再看看题吧。发现题目中其实有一个很重要的信息，那就是每次可以被移除的是一个回文子序列。不是回文子字符串，不是回文子字符串，不是回文子字符串！重要的事情说三编。凑字数
为什么我会说这一个信息非常重要呢，重要到直接回归到了 EASY 的难度。下面我们举个例子吧：
现在我有一个原始字符串是 ‘aababbaabaabbabbaaabbabbbaabba’。那么它的子字符串是什么，就是截取其中连续的一串，例如 ‘babbaa’。而它的子序列是什么呢，就是不打乱顺序的从中随意取出字符，凑成一串，例如 ‘aaaa’。
相信看到这里，小伙伴们应该明白为什么说难度一下子降到 EASY 了吧。虽然题目有要求是回文子序列，可是如果我的子序列中只包含一种类型的字符，例如只包含 ‘a’ 或者 ‘b’，那无论长度是多少，都是回文字符串了。再然后，原始字符串只由 ‘a’ 和 ‘b’ 这两种字母组成。也就是说…其实我们最多只需要两次就可以删空整个原始字符串了。
是不是非常的鹅妹子嘤！哈哈哈哈，机智的小猪又有借口可以吃薯片啦 >.<
直接方案
上面我们分析出了解题思路，以及最大的次数是 2。那么具体什么情况下是 0、1 和 2 呢。
- 0 的话非常直白，如果原始字符串本身为空，那么我们需要的次数就是 0。
- 1 的话意味着我们一次就删掉了所有内容，但我们只能删掉回文子序列，那么也就是说如果原始字符串本身就是一个回文字符串，那么我们需要的次数就是 1。
- 2 的话剩下的其他字符串就是需要两次即可，原理在上面的思路种已经分析过啦。
到了这一步，相信小伙伴们可以轻松的给出实现流程了吧。具体如下：
- 判断原始字符串是否为空，如果是则返回 0。
- 判断原始字符串是否为回文字符串，如果是则返回 1。
- 返回 2。
基于这个流程，我们可以实现类似下面的代码：
const removePalindromeSub = s => {
if (s.length === 0) return 0;
for (let left = 0, right = s.length - 1; left < right; ++left, --right) {
if (s[left] !== s[right]) return 2;
}
return 1;
};当然我们也可以一行代码来实现，只不过判断回文的逻辑需要做一点变化。也就是通过把原始字符串反序然后和自身比较来判断是否是回文字符串。具体一行实现的代码如下：
const removePalindromeSub = s => s.length === 0 ? 0 : s.split('').reverse().join('') === s ? 1 : 2;总结
说实话最开始小猪是有被题目吓到。因为按照惯例第一题应该是个送分题鸭，怎么一上来就是回文字符串什么的。仔细看题之后才发现其中的玄机。正应征了，鲁迅曾经可能没说过，『看题不仔细，做题两行泪』。小伙伴们可不要学小猪这样为了吃薯片不好好看题鸭。
加油武汉，天佑中华
相关链接
统计信息
| 通过次数 | 提交次数 | AC比率 |
|---|---|---|
| 9916 | 14373 | 69.0% |
提交历史
| 提交时间 | 提交结果 | 执行时间 | 内存消耗 | 语言 |
|---|
