# 1332. Remove Palindromic Subsequences
# Easy

# 449

# 950

# Add to List

# Share
# 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'




# This approach does not work:

# class Solution:
#     def removePalindromeSub(self, s: str) -> int:
        
#         def is_palindrome(left, right):

#             while left < right:
#                 if s[left] != s[right]:
#                     return False
#                 left += 1
#                 right -= 1
#             return True
        
#         def helper(start, end):
#             if start > end:
#                 return 0
#             if start == end:
#                 return 1
#             if is_palindrome(start, end):
#                 return 1
#             min_ops = float('inf')
#             for s in range(start, end+1):
#                 for e in range(s+1, end+1):
#                     # print(s[start:end], s[:start] + s[end:])
#                     min_ops = min(min_ops, helper(s, e) + helper(start, s-1) + helper(e+1, end))
#             return min_ops
                
#         return helper(0, len(s)-1)
            
        


# This solution works:

class Solution:
    def removePalindromeSub(self, s: str) -> int:
        '''
        There are only a and b - so its either 0, 1, 2
        all of them get deleted within 2 
        because its subsequence - we can choose however we want it
        brute force is you can delete all a to leave all b
        0 is when its empty
        1 is when its palindrome
        2 is else
        '''
        if not s:
            return 0
        l = 0
        r = len(s)-1
        while l < r:
            if s[l] != s[r]:
                return 2
            l += 1
            r -= 1
        return 1