class Solution:
  def findMinimumDeletions(self, st):
    def is_palindrom(s):
        i = 0
        j = len(s) - 1
        while i <= j:
          if s[i] != s[j]:
            return False
          i += 1
          j -= 1
        return True
    
    def dp(s, memo):
      if s in memo:
        return memo[s]

      if is_palindrom(s):
        return len(s)
      
      max_len = 0
      for i in range(len(s)):
        max_len = max(dp(s[:i] + s[i + 1:], memo), max_len)
      
      memo[s] = max_len

      return max_len
      
    return len(st) - dp(st, {})