LeetCode 1332 : palindromic subsequence [解決]を削除する

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 <= 1000
• s only consists of letters 'a' and 'b'

Did you get the question? If yes, then you are a PRO, if not then don't worry, you are normal, like me. So before understanding the question, let's first understand what are subsequence and palindrome.

We are going to use the below ideas to solve this question:

1. If any string is empty, then we don't need to do anything and return 0 .
2. If a string is a palindrome then we can delete the whole string in a single operation as a string is also a subsequence of itself. For such case, we need to return 1 .
3. A string of any length consists of a single type of character is always a subsequence eg. aaaaa , bbb , a etc.
4. So, I can delete a subsequence containing all characters of the same type from the string. eg. from string aaabbbababa I can remove aaaaaa as it's a subsequence and palindrome as well.
5. And surprise, we are left with the string bbbbb which is also a palindrome so we can delete this in a single operation.
6. As the string can contain only 'a' or 'b' only. So if the string is not palindrome then I can delete all the 'a' s in the first pass then all the 'b' s in the second pass, so the max operations we need is 2 if the string is not a palindrome.

C++ Code:

class Solution {
public:
    int removePalindromeSub(string s) {
        // Check if string is empty
        if(s.empty())
            return 0;

        int len=s.size();

        // Check for pallindrome
        for(int i=0; i<=len/2; i++){
            // If not pallindrome then 2 operations are needed
            if(s[i] != s[len-i-1])
                return 2;
        }
        // If pallindrome then only one operation is needed
        return 1;
    }
};

Runnable C++ Code: