难度: Easy
给你一个字符串 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'运行时间: 23 ms
内存: 16.1 MB
class Solution:
def removePalindromeSub(self, s: str) -> int:
return 1 if s == s[::-1] else 2
题解的核心思路在于最多只需要两步删除操作即可删除所有字符。如果字符串本身是一个回文，那么一次删除操作就足够了；如果不是回文，可以先删除所有的'a'或所有的'b'作为一个回文子序列，然后再删除剩余的字符，即最多两步。因此，该题解首先检查字符串是否为回文，如果是，则返回1，表示一次删除；如果不是，返回2，表示需要两次删除。
时间复杂度: O(n)
空间复杂度: O(1)
class Solution:
def removePalindromeSub(self, s: str) -> int:
# 检查字符串s是否为回文
if s == s[::-1]:
# 如果s是回文，则只需1次删除
return 1
# 如果s不是回文，需要2次删除：一次删除所有'a'，一次删除所有'b'
return 2
在这个问题中，我们只考虑包含字符'a'和'b'的字符串。回文子序列是指子序列本身是回文的序列。考虑到最坏的情况，即字符串完全不是回文，我们可以首先删除所有'a'组成的子序列，因为这是一个回文子序列（'aaaa'等）。剩下的必然是所有'b'组成的子序列，这同样是一个回文子序列。因此，不论字符串的具体内容如何，最多两次操作就能删除整个字符串。第一次删除所有'a'，第二次删除所有'b'。
在这道题中，选择首先删除'a'还是'b'实际上并没有区别。因为目标是最小化删除次数而非删除的字符数量，无论先删除哪个字符，最终都是需要两步来删除非回文字符串（如果字符串不是回文的话）。首先删除'a'或'b'都将剩下一个纯单一字符的字符串，这仍然是一个回文子序列，可以在第二步中被删除。
检查字符串是否为回文通常需要O(n)的时间复杂度，其中n是字符串的长度，因为需要比较字符串的前半部分和反转的后半部分。对于非常长的字符串，这种方法已经是相对高效的。然而，如果需要进一步优化，可以考虑使用多线程或并行处理的方式来同时从头部和尾部开始比较，尽管这种优化在大多数实际情况下并不是必要的，因为字符串长度通常是可管理的。
如果字符串由单一字符重复组成，如'aaaa'或'bbbb'，这种字符串本身就是一个回文子序列。因此，根据题解，这种情况下只需要一步删除操作即可。这个特殊情况完全符合题解中的逻辑，即如果字符串是回文，则一次删除操作足够。