'''
keys: 
Solutions:
Similar: 
T:
S:
'''
from typing import List


class Solution:
    # dp[i][j]: the longest palindromic subsequence's length of 
    # substring(i, j), here i, j represent left, right indexes in the string
    # dp[i][j] = dp[i+1][j-1] + 2 if s[i] == s[j]
    # otherwise: dp[i][j] = max(dp[i+1][j], dp[i][j-1])
    # initialization: dp[i][i] = 1
    def longestPalindromeSubseq1(self, s: str) -> int:
        n = len(s)
        dp = [[0] * n for _ in range(n)]
        
        for i in range(n-1, -1, -1):
            dp[i][i] = 1
            for j in range(i+1, n):
                if s[i] == s[j]:
                    dp[i][j] = dp[i+1][j-1] + 2
                else:
                    dp[i][j] = max(dp[i+1][j], dp[i][j-1])
        return dp[0][n-1]
    
    
    # huahua
    def longestPalindromeSubseq3(self, s: str) -> int: 
        n = len(s)
        dp = [[0] * n for _ in range(n)]
        
        for l in range(1, n+1): # l: length of subsequence
            for i in range(n - l + 1): # i: starting position of subsequence
                j = i + l - 1 # j: ending position of subsequence
                if i == j: 
                    dp[i][j] = 1 # base case
                    continue
                if s[i] == s[j]:
                    dp[i][j] = dp[i+1][j-1] + 2
                else:
                    dp[i][j] = max(dp[i+1][j], dp[i][j-1])
        return dp[0][n-1]
            
    
    # top-bottom recursion with memo
    def longestPalindromeSubseq2(self, s: str) -> int: 
        n = len(s)
        memo = [[0] * n for _ in range(n)]
        return self.helper(s, 0, n-1, memo)
    
    def helper(self, s, i, j, memo):
        if memo[i][j]:
            return memo[i][j]
        if i > j: return 0
        if i == j: return 1
        if s[i] == s[j]:
            memo[i][j] = self.helper(s, i+1, j-1, memo) + 2
        else:
            memo[i][j] = max(self.helper(s, i+1, j, memo), \
                             self.helper(s, i, j-1, memo))
        return memo[i][j]
    
    
    
        
        
    
    
    # brute force, O(2^n), how does this consider subsequence cases
    # i.e., bbbab -> bbbb ?
    # https://leetcode.com/problems/longest-palindromic-subsequence/discuss/99111/Evolve-from-brute-force-to-dp
    def longestPalindromeSubseq(self, s: str) -> int:
        return self.helper(0, len(s)-1, s)
    
    def helper(self, l, r, s):
        if l == r: return 1
        if l > r: return 0
        return 2 + self.helper(l+1, r-1, s) if s[l] == s[r] else\
            max(self.helper(l+1, r, s), self.helper(l, r-1, s))