1332. 删除回文子序列

题意：给你一个字符串 s，它仅由字母 'a' 和 'b' 组成。每一次删除操作都可以从 s 中删除一个回文 子序列。
返回删除给定字符串中所有字符（字符串为空）的最小删除次数。
「子序列」定义：如果一个字符串可以通过删除原字符串某些字符而不改变原字符顺序得到，那么这个字符串就是原字符串的一个子序列。
「回文」定义：如果一个字符串向后和向前读是一致的，那么这个字符串就是一个回文。

解题思路

解法1：
1.由题意可知，子序列定义为，不改变原有顺序即可,只有字符a、b，所以问题很简单了，我们只需关注a、b出现的次数
2.如果a或者b出现偶数次，则第一次删除a或者b，剩下的肯定是一个单字符的回文字符串，删除即可，这种情况下删除2次
3.如果a和b都出现奇数次，则第一次删除a和1个b，剩下的肯定是一个偶数的单字符回文字符串，删除接口，这二种情况下删除2次
4.其余情况，只需删除1次即可

解法2：
1.如果s为空,一次不用
2.如果s为回文,一次
3.如果s非回文,两次(任意多的a和任意多的b都是回文,故两次)

image.png

解题遇到的问题

无

后续需要总结学习的知识点

无

##解法1
class Solution {
    public int removePalindromeSub(String s) {
        if (s == null || s.length() <= 1) {
            return s.length();
        }

        if (isPalindrome(s)) {
            return 1;
        }
        // 由题意可知，子序列定义为，不改变原有顺序即可，也就是说，原有字符串中如果是偶数倍出现的字符，都可以第一次删除，奇数倍出现的字符，可以在第一次删除过程中，先删除-1个，剩余一个单独清除
        // 由题意可知，只有字符a、b，所以问题很简单了，我们只需关注a、b出现的次数
        int a = 0, b = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == 'a') {
                a++;
            } else {
                b++;
            }
        }
        if (a % 2 == 0 || b % 2 == 0 || (a % 2 != 0 && b % 2 != 0)) {
            return 2;
        } else {
            return 1;
        }
    }

    public boolean isPalindrome(String s) {
        int i = 0, j = s.length() - 1;
        while (i < j) {
            if (s.charAt(i) != s.charAt(j)) {
                return false;
            }
            i++;
            j--;
        }
        return true;
    }
}

##解法2
class Solution {
    public int removePalindromeSub(String s) {
        if (s == null || s.length() <= 1) {
            return s.length();
        }

        if (isPalindrome(s)) {
            return 1;
        }

        return 2;
    }

    public boolean isPalindrome(String s) {
        int i = 0, j = s.length() - 1;
        while (i < j) {
            if (s.charAt(i) != s.charAt(j)) {
                return false;
            }
            i++;
            j--;
        }
        return true;
    }
}