class Solution:
  def findLPSLength(self, st):
    
    def is_palindrom(s, i, j):
      while i <= j:
        if s[i] != s[j]:
          return False
        i += 1
        j -= 1
      return True

    def dp(s, i, j, memo):
      if (i, j) in memo:
        return memo[(i, j)]

      if is_palindrom(s, i, j):
        return j - i + 1
      
      if i > j:
        return 0 

      result = max(dp(s, i + 1, j, memo), dp(s, i, j - 1, memo))
      
      memo[(i, j)] = result
      
      return result

    return dp(st, 0, len(st) - 1, {})