Remove Palindromic Subsequences

To solve this problem, we need to make observations about how the operations can be made. Since the problem allows us to remove a palindromic subsequence, not substring, this means we are allowed to remove non-continuous sequences of characters.

Given the string s, if it is a palindrome itself, we can remove the entire string in one operation. Otherwise, we can always complete the operation in two steps: remove all ‘a’s, then remove all ‘b’s, or vice versa. Both ‘a’ and ‘b’ are palindromic subsequences.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution:
    def removePalindromeSub(self, s: str) -> int:
        # If the string is empty, we return 0 since no operations are needed
        if not s:
            return 0

        # Check if the string is a palindrome
        if s == s[::-1]:
            return 1

        # If the string is not a palindrome, we can remove all 'a's and then 'b's, or vice versa.
        return 2