本文共 1931 字，大约阅读时间需要 6 分钟。

1. 问题描述：

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

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

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

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

示例 1：

输入：s = "ababa"

输入：s = "abb"

输入：s = "baabb"

输入：s = ""

提示：

0 <= s.length <= 1000

来源：力扣（LeetCode）

2. 思路分析：

这道题目主要是需要理解清楚题目，理解清楚之后其实还是很简单的，一开始的做法是傻傻的模拟整个的过程，尝试删除其中的字符，其实题目中已经明确告诉了是子序列所以我们可以第一次检查整个字符串是否是回文串假如是回文串那么直接返回1，如何不是说明需要两次进行删除，第一次删除所有的a，第二次删除所有的b

3. 代码如下：

模拟代码：

class Solution {    public int removePalindromeSub(String s) {        int res = 0;        while (s.length() > 0){            StringBuilder sb = new StringBuilder(s);            if (s.equals(sb.reverse().toString())) return ++res;            for (int i = 1; i < s.length(); ++i){                String t = s.substring(0, i);                int len = getlen(t);                String t2 = s.substring(i);                int len2 = getlen(t2);                if (len < 0) {                    s = t2;                    break;                }                else if (len2 < 0){                    s = t;                    break;                }                s = t.length() > t2.length() ? t : t2;            }            ++res;        }        return res;    }    private static int getlen(String t) {        for (int i = 0, j = t.length() - 1; i < t.length() / 2; ++i, --j){            if (t.charAt(i) != t.charAt(j)) return -1;        }        return t.length();    }}

优化代码：

class Solution {    public int removePalindromeSub(String s) {        StringBuilder sb = new StringBuilder(s);        if (s.equals("")) return 0;        if (s.toString().equals(sb.reverse().toString())) return 1;        return 2;    }}