题目

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

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

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

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

来源：力扣（LeetCode）

解答

首先要明确题意，题目要求的为“子序列”而非“子字符串”，即允许有间隔的字母连接起来。

其次，字符串只由a和b组成，所以最多需要两次：因为纯a是一个回文序列，纯b同理，所以最多两次就可以将所有字母都删掉。

所以只需判定给定字符串s是否回文即可，回文返回1，不回文返回2。

代码如下：

class Solution {
public:
    int removePalindromeSub(string s) {
        int i = 0;
        int j = s.size() - 1;

        while (i < j) {
            if (s[i] != s[j]) {
                return 2;
            }
            i++;
            j--;
        }

        return 1;
    }
};