class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        def lcs(s1, s2):
            n = len(s1)
            m = len(s2)
            dp = [[-1] * (m + 1) for i in range(n + 1)]
            for i in range(n + 1):dp[i][0] = 0
            for i in range(m + 1): dp[0][i] = 0
            for ind1 in range(1, n + 1):
                for ind2 in range(1, m + 1):
                    if s1[ind1 - 1] == s2[ind2 - 1]:
                        dp[ind1][ind2] = 1 + dp[ind1 - 1][ind2 - 1]
                    else:
                        dp[ind1][ind2] = max(dp[ind1 - 1][ind2], dp[ind1][ind2 - 1])
            return dp[n][m]
#printing
def lcs(s1, s2):
    n = len(s1)
    m = len(s2)
    
    dp = [[0 for j in range(m + 1)] for i in range(n + 1)]
    for i in range(n + 1):
        dp[i][0] = 0
    for i in range(m + 1):
        dp[0][i] = 0

    for ind1 in range(1, n + 1):
        for ind2 in range(1, m + 1):
            if s1[ind1 - 1] == s2[ind2 - 1]:
                dp[ind1][ind2] = 1 + dp[ind1 - 1][ind2 - 1]
            else:
                dp[ind1][ind2] = 0+max(dp[ind1 - 1][ind2], dp[ind1][ind2 - 1])

    len_ = dp[n][m]
    i = n
    j = m
    
    index = len_ - 1
    str_ = ""
    for k in range(1,1+len_):
      str_+="$" #dummy string
    
    while i > 0 and j > 0:
        if s1[i - 1] == s2[j - 1]:
            str_ = s1[i - 1] + str_[:-1]
            index -= 1
            i -= 1
            j -= 1
        elif s1[i - 1] > s2[j - 1]:
            i -= 1
        else:
            j -= 1
    
    print("The Longest Common Subsequence is", str_)
#memo
class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        def f(i1,i2,dp):
            if i1<0 or i2<0:return 0
            if dp[i1][i2]!=-1:return dp[i1][i2]
            if text1[i1]==text2[i2]:
                dp[i1][i2] = 1+f(i1-1,i2-1,dp)
                return dp[i1][i2]

            else:
                dp[i1][i2] = max(f(i1,i2-1,dp),f(i1-1,i2,dp))
                return dp[i1][i2]

        dp = [[-1 for i in range(len(text2))] for j in range(len(text1))]
        return f(len(text1)-1,len(text2)-1,dp)