題目描述：
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".
Example 4:
Input: s = ""
Output: 0
Constraints:
0 <= s.length <= 1000sonly consists of letters ‘a’ and ‘b’
題解：
這題雖然是Easy，但是真的太tricky了。做這一題之前，首先要了解一個事，就是”Subsequence”的本質。
Subsequence – 子字符串，這個子符串可以是在字符串中「不連續」的字符。那就代表在”abbaba”中，我可以直接把”bbb”當成Palindromic Subsequence移除掉，然後再剩下的Palindromic Subsequence – “aaa”移除，總共2步。也就是說，既然本題提供的字符串只有’a’和’b’兩種字符，在每次移除一個Palindromic Subsequence的設定下，移除所有字符的步數上限為2。
因此，我們唯一要檢查的就只有：
- 字符串是否為空，空則返回0。
- 字符串是否一開始就是互文，是則直接整段移除。
居然就只是這樣而已，我一開始還想著怎樣把”abb”和”baabb”這樣的互文在後面部分和前面部分的情況區分開來，然後每移除一次，Step數+1，最後返回Step，但原來是我想的太複雜了，這題真的太tricky了……
Subsequence的定義參考：https://en.wikipedia.org/wiki/Subsequence
“The list of all subsequences for the word “apple” would be “a“, “ap“, “al“, “ae“, “app“, “apl“, “ape“, “ale“, “appl“, “appe“, “aple“, “apple“, “p“, “pp“, “pl“, “pe“, “ppl“, “ppe“, “ple“, “pple“, “l“, “le“, “e“, “” (empty string).”
public class Solution {
public int RemovePalindromeSub(string s) {
//如果字符串為空，返回0
if(s.Length == 0){return 0;}
//本身是互文，直接1步移除全部字符
if(IsPalindrome(s)){return 1;}
//如果不是互文，則分別移除所有a字符和b字符，共2步
return 2;
}
//檢查互文
bool IsPalindrome(string s)
{
int left = 0;
int right = s.Length - 1;
while(left < right)
{
if(s[left] != s[right]){ return false; }
left++;
right--;
}
return true;
}
}