1332 Remove Palindromic Subsequences

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.

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: String is already palindrome

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 <= 1000

• s[i] is either 'a' or 'b'.

一看下去以为是难题，然后看完栗子，发现，是不是只会返回1或者2。如果是回文就返回1，不是就返回2。rationale 因为只有两种字母，而且是subsequence，所以最坏的情况下就第一次把a全删掉，第二次把b全删掉。所以这题其实可以转化成回文的判断。T:O(n), S:O(1)

public int removePalindromeSub(String s) {
    if (s == null || s.isEmpty()) {
        return 0;
    }

    int i = 0;
    int j = s.length() - 1;
    boolean isPar = true;
    while (i < j) {
        if (s.charAt(i) != s.charAt(j) && j - i > 1) {
            isPar = false;
            break;
        }
        i++;
        j--;
    }

    return isPar ? 1 : 2;
}