Given two strings text1 and text2, return the length of their longest common subsequence.
A subsequence of a string is a new string generated from the original string with some characters(can be none) deleted without changing the relative order of the remaining characters. (eg, "ace" is a subsequence of "abcde" while "aec" is not). A common subsequence of two strings is a subsequence that is common to both strings.
 
If there is no common subsequence, return 0.
 
Example 1:
Input: text1 = "abcde", text2 = "ace" 
Output: 3  
Explanation: The longest common subsequence is "ace" and its length is 3.

Example 2:
Input: text1 = "abc", text2 = "abc"
Output: 3
Explanation: The longest common subsequence is "abc" and its length is 3.

Example 3:
Input: text1 = "abc", text2 = "def"
Output: 0
Explanation: There is no such common subsequence, so the result is 0.

 
Constraints:

1 <= text1.length <= 1000
1 <= text2.length <= 1000
The input strings consist of lowercase English characters only.

Difficulty: interview

Starter code:

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        

Solutions:
class Solution:
    def longestCommonSubsequence(self, a: str, b: str) -> int:
        last, current = [0] * (len(b) + 1), [0] * (len(b) + 1)
        
        for i in range(len(a) - 1, -1, -1):
            for j in range(len(b) - 1, -1, -1):
                if a[i] == b[j]:
                    current[j] = 1 + last[j + 1]
                else:
                    current[j] = max(last[j], current[j + 1])
            last = current
            current = [0] * (len(b) + 1)
        return last[0]

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        n, m = len(text1), len(text2)
        
        if n == 0 or m == 0:
            return max(n, m)
        
        DeleteT1 = 0
        DeleteT2 = 1
        Match = 2
        
        dp = [[(0, None) for j in range(m+1)] for i in range(n+1)]  ###(value, direction)
        
        for i in range(1,n+1):
            dp[i][0] = (i,DeleteT1)
        for j in range(1,m+1):
            dp[0][j] = (j,DeleteT2)
            
        for i in range(1, n+1):
            for j in range(1, m+1):
                if text1[i-1] == text2[j-1]:
                    dp[i][j] = (dp[i-1][j-1][0],Match)
                    continue
                
                val = min(dp[i-1][j][0], dp[i][j-1][0])
                if val == dp[i-1][j][0]:  ###not dp[i-1][j]
                    dp[i][j] = (val+1,DeleteT1)
                else:
                    dp[i][j] = (val+1,DeleteT2)
        
        #print(len(dp), len(dp[0]))
        #print(dp)
        i,j = n,m
        T1Length = n
        while i >= 0 and j >= 0:
            comb = dp[i][j]
            if comb[1] == DeleteT1:
                i -= 1
                T1Length -= 1
            elif comb[1] == DeleteT2:
                j -= 1
            else:
                i -= 1
                j -= 1
        
        #print(dp)
        return T1Length

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        
        s1,s2=text1,text2
        len_s1,len_s2=len(s1),len(s2)
        pick_s1_or_s2,pick_s1,pick_s2=0,1,2
        
        
        match_table=[[0 for i in range(len_s2)] for j in range(len_s1)]
        
        for i in range(len_s1):
            for j in range(len_s2):
                
                if(s1[i]==s2[j]):
                    
                    if(i==0 or j==0):
                        match_table[i][j]=1
                    
                    else:
                        match_table[i][j]=1+match_table[i-1][j-1]
                else:
                    if(i==0 and j>0):
                        match_table[i][j]=match_table[i][j-1]
                    elif(j==0 and i>0):
                        match_table[i][j]=match_table[i-1][j]
                    elif(i>0 and j>0):
                        if(match_table[i-1][j]>match_table[i][j-1]):
                            match_table[i][j]=match_table[i-1][j]
                        else:
                            match_table[i][j]=match_table[i][j-1]
        return match_table[len_s1-1][len_s2-1]
                        
        
        
                                      
        


class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        dp = [[0 for i in range(len(text1)+1)] for j in range(len(text2)+1)]
        for i in range(1,len(dp)):
            for j in range(1,len(dp[0])): # in case of letter out of boarder 
                dp[i][j] = max(dp[i-1][j],dp[i][j-1])
                if text2[i-1] == text1[j-1]: # one more letter to sub sequence
                    dp[i][j] = dp[i-1][j-1] + 1 
        return dp[-1][-1]

class Solution:
    def recursiveLCS(self, t1, t2):
        if not t1 or not t2:
            return 0
        else:
            if t1[0] == t2[0]:
                return 1 + self.recursiveLCS(t1[1:], t2[1:])
            else:
                left = self.recursiveLCS(t1[1:], t2)
                right = self.recursiveLCS(t1, t2[1:])
                return max(left, right)
        
    def recursiveLongestCommonSubsequence(self, text1: str, text2: str) -> int:
        return self.recursiveLCS(text1, text2)
    

    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        # maybe do checks here but can probably get passed it
        DP = [[0]*(len(text2)+1) for i in range(len(text1)+1)]
        # MAYBE DO BASE CASES TO PRACTICE
        for i in range(1, len(text1)+1):
            for j in range(1, len(text2)+1):
                if text1[i-1] == text2[j-1]:
                    DP[i][j] = 1 + DP[i-1][j-1]
                else:
                    left = DP[i-1][j]
                    right = DP[i][j-1]
                    DP[i][j] = max(left, right)
        for row in DP:
            print(row)
        return DP[len(text1)][len(text2)]
        
        


from collections import defaultdict
class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        dp = defaultdict(int)
        
        for i in range(len(text1)):
            for j in range(len(text2)):
                if text1[i] == text2[j]:
                    dp[(i, j)] = 1 + dp[(i-1, j-1)]
                else:
                    dp[(i, j)] = max(dp[(i-1, j)], dp[(i, j-1)])
                    
        return dp[(len(text1)-1, len(text2)-1)]

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        str1, str2 = text1, text2

        num_rows = len(str1) + 1
        num_cols = len(str2) + 1
        lengths = [[0 for _ in range(num_cols)] for _ in range(num_rows)]
        for row in range(1, num_rows):
            for col in range(1, num_cols):
                if str1[row - 1] == str2[col - 1]:
                    lengths[row][col] = lengths[row - 1][col - 1] + 1
                else:
                    lengths[row][col] = max(lengths[row - 1][col], lengths[row][col - 1])

        return lengths[-1][-1]


class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        m, n = len(text1), len(text2)
        dp = [[0] * (n + 1) for i in range(m + 1)]
        
        for i in range(m + 1):
            for j in range(n + 1):
                if i != 0 and j != 0:
                    if text1[i - 1] == text2[j - 1]:
                        dp[i][j] = dp[i - 1][j - 1] + 1
                    dp[i][j] = max(dp[i][j], max(dp[i - 1][j], dp[i][j - 1]))
        return dp[-1][-1]


import numpy as np
#from functools import lru_cache
class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        if len(text1) == 0 or len(text2) == 0:
            return 0
        
        m = len(text1)
        n = len(text2)
        #return self.dp(text1, text2, m-1, n-1)
        
        A = np.zeros((m+1, n+1),int)
        
        for i in range(1,m+1):
            for j in range(1,n+1):
                if text1[i-1] == text2[j-1]:
                    A[i,j] = A[i-1,j-1] +1
                else:
                    A[i,j] = max(A[i-1,j], A[i,j-1])
        return A[-1,-1]
        
    # @lru_cache(maxsize=None)
    # def dp(self, text1, text2, i, j):
    #     if i  < 0 or j < 0:
    #         return 0
    #     if text1[i] == text2[j]:
    #         return self.dp(text1, text2, i-1, j-1) + 1
    #     else:
    #         return max(self.dp(text1, text2, i-1, j), self.dp(text1, text2, i, j-1))


class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        dp = [[0]*(len(text2)+1) for i in range(len(text1)+1)]
        
        dp[0][0] = 0
        
        for i in range(1, len(dp)):
            for j in range(1, len(dp[0])):
                if text1[i-1] == text2[j-1]:
                    dp[i][j] = dp[i-1][j-1] + 1
                else:
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])
        
        return dp[len(text1)][len(text2)]
            
    
    
    
    # $ a c e
    # a
    # b
    # c
    # d
    # e


class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        m=len(text1)
        n=len(text2)
        t=[[0 for i in range(n+1)] for j in range(m+1)]
        for i in range(1,m+1):
            for j in range(1,n+1):
                if text1[i-1]==text2[j-1]:
                    t[i][j]=1+t[i-1][j-1]
                else:
                    t[i][j]=max(t[i][j-1],t[i-1][j])
        return t[-1][-1]


class Solution:
    # approach 3
    def longestCommonSubsequence(self, s1: str, s2: str) -> int:
        def print_grid(grid):
            for row in grid:
                print(row)
        
        dp_row = [0] * (len(s2) + 1)
        dp_row_pre = [0] * (len(s2) + 1)
        N, M = len(s1), len(s2)
        for i in range(N - 1, -1, -1):
            for j in range(M - 1, -1, -1):
                if s1[i] == s2[j]:
                    dp_row[j] = dp_row_pre[j + 1] + 1
                else:
                    dp_row[j] = max(dp_row_pre[j], dp_row[j + 1])
            dp_row_pre, dp_row = dp_row, dp_row_pre
                # print(\"update row=\", i, \", col=\", j)
                # print_grid(dp_grid)
        return dp_row_pre[0]
        
    # approach 1: recursive memorization
#     def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        
#         @lru_cache(maxsize=None)
#         def memo_solve(p1, p2):
#             if p1 == len(text1) or p2 == len(text2):
#                 return 0
            
#             # option 1: we don't include text1[p1] in the solution
#             option_1 = memo_solve(p1 + 1, p2)
            
#             # option 2: we include p1 in the solution, as long as there is a match in p2
#             first_occurrence = text2.find(text1[p1], p2)
#             option_2 = 0
#             if first_occurrence != -1:
#                 option_2 = 1 + memo_solve(p1 + 1, first_occurrence + 1)
            
#             return max(option_1, option_2)
        
#         return memo_solve(0, 0)
    
      # approach 2
#     def longestCommonSubsequence(self, s1: str, s2: str) -> int:
        
#         @lru_cache(maxsize=None)
#         def mem_solve(p1: int, p2: int) -> int:
#             # base case 
#             if p1 == len(s1) or p2 == len(s2):
#                 return 0
            
#             # option 1 match the first letter
#             if s1[p1] == s2[p2]:
#                 return 1 + mem_solve(p1 + 1, p2 + 1)
            
#             # option 2
#             return max(mem_solve(p1, p2 + 1), mem_solve(p1 + 1, p2))
        
#         return mem_solve(0, 0)
        


from functools import lru_cache
class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        
        
        l1 = len(text1)
        l2 = len(text2)
        
        memo = [[0 for _ in range(max(l1,l2)+1)] for _ in range(max(l1,l2)+1)]
        
        
        current=0
        
        for i in range(1,l1+1):
            for j in range(1,l2+1):
                
                current = memo[i-1][j-1]
                
                if text1[i-1]==text2[j-1]:
                    memo[i][j]=1+memo[i-1][j-1]
                else:
                    memo[i][j]=max(memo[i-1][j],memo[i][j-1])
                
                current=max(memo[i][j],current)
 
        
        return current
                
            
            


class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        
        m = len(text1)
        n = len(text2)
        
        dp = [[0 for i in range(n+1)] for j in range(m+1)]
        
        for i in range(1,m+1):
            for j in range(1,n+1):
                if text1[i-1]==text2[j-1]:
                    dp[i][j] = dp[i-1][j-1]+1
                else:
                    dp[i][j] = max(dp[i-1][j],dp[i][j-1])
                    
        return dp[m][n]
        


import numpy as np
class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        if len(text1) == 0 or len(text2) == 0:
            return 0
        
        m = len(text1)
        n = len(text2)
        
        A = np.zeros((m+1, n+1),int)
        
        for i in range(1,m+1):
            for j in range(1,n+1):
                if text1[i-1] == text2[j-1]:
                    A[i,j] = A[i-1,j-1] +1
                else:
                    A[i,j] = max(A[i-1,j], A[i,j-1])
        return A[-1,-1]


class Solution:
    # def longestCommonSubsequence(self, text1: str, text2: str) -> int:
    #     matrix = [[None]*(len(text2)+1) for i in range(len(text1)+1)]
    #     for j in range(len(text2)+1):
    #         matrix[0][j] = 0
    #     for i in range(len(text1)+1):
    #         matrix[i][0] = 0
    #     for i in range(1, len(text1)+1):
    #         for j in range(1, len(text2)+1):
    #             if text1[i-1] == text2[j-1]:
    #                 matrix[i][j] = 1 + matrix[i-1][j-1]
    #             else:
    #                 matrix[i][j] = max(matrix[i-1][j], matrix[i][j-1])
    #     return matrix[len(text1)][len(text2)]
    
    
    
    
    
    

    
    
    


    def longestCommonSubsequence(self, s1, s2):
        def _longest_common_subsequence(i, j, cache):
            if i < 0 or j < 0:
                return 0
            elif cache[i][j] != None:
                return cache[i][j]
            elif s1[i] == s2[j]:
                answer = 1 + _longest_common_subsequence(i-1, j-1, cache)
                cache[i][j] = answer
                return answer
            else:
                answer = max(_longest_common_subsequence(i, j-1, cache), _longest_common_subsequence(i-1, j, cache))
                cache[i][j] = answer
                return answer
        return _longest_common_subsequence(len(s1)-1, len(s2)-1, [[None]*len(s2) for i in range(len(s1))])

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        l1, l2 = len(text1), len(text2)
        dp = [[0]*l2 for i in range(l1)]
        
        get = lambda r, c: 0 if -1 in [r, c] else dp[r][c]
        
        for r, c1 in enumerate(text1): # pos, char
            for c, c2 in enumerate(text2):              
                
                if c1 == c2:
                    dp[r][c] = get(r-1, c-1) + 1
                else:
                    dp[r][c] = max(get(r-1, c), get(r, c-1))
               
        for i in dp:
            print(i)
        return dp[-1][-1]
                        


class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        
        n = len(text1)
        m = len(text2)
        
        dp = []
        
        for i in range(n):
            dp.append([-1]*m)
        
        def lcs(i,j):
            
            if(i>=n or j>=m):
                return 0
            
            if(dp[i][j]!=-1):
                return dp[i][j]
            
            if(text1[i]==text2[j]):
                ans = 1 + lcs(i+1,j+1)
            else:
                ans = max(lcs(i+1,j),lcs(i,j+1))
            
            dp[i][j] = ans
            
            return ans
        return lcs(0,0)


class Solution:
    def longestCommonSubsequence(self, text1, text2):


        def compute(x, y):
            if x == len(text1):
                return 0
            if y == len(text2):
                return 0

            if text1[x] == text2[y]:
                return 1 + compute(x+1, y+1)

            return max([compute(x+1, y), compute(x, y+1)])

        cache = {}

        for x in range(-1, len(text1)+1):
            cache[(x, -1)] = 0

        for y in range(-1, len(text2)+1):
            cache[(-1, y)] = 0

        for x in range(len(text1)):
            for y in range(len(text2)):
                if text1[x] == text2[y]:
                    cache[(x, y)] = 1 + cache[(x-1, y-1)]
                else:
                    cache[(x, y)] = max([cache[(x, y-1)], cache[(x-1, y)]])

        return cache[(len(text1)-1, len(text2)-1)]


class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        if len(text1) == 0 or len(text2) == 0:
            return 0
        
#         grid = [[[None, 0, None, None] for i in range(len(text1) + 1)] for i in range(len(text2) + 1)] 
        
#         for i in range(1, len(text2) + 1):
#             for j in range(1, len(text1) + 1):
#                 if text1[j - 1] == text2[i - 1]:
#                     grid[i][j] = [text2[i - 1], grid[i - 1][j - 1][1] + 1, i - 1, j - 1]
#                 else:
#                     if grid[i - 1][j][1] > grid[i][j - 1][1]:
#                         grid[i][j] = [None, grid[i - 1][j][1], i - 1, j]
#                     else:
#                         grid[i][j] = [None, grid[i][j - 1][1], i, j - 1]
#         return grid[-1][-1][1]
    
    
        grid = [[[0] for i in range(len(text1) + 1)] for i in range(len(text2) + 1)] 
        
        for i in range(1, len(text2) + 1):
            for j in range(1, len(text1) + 1):
                if text1[j - 1] == text2[i - 1]:
                    grid[i][j] = [grid[i - 1][j - 1][0] + 1]
                else:
                    if grid[i - 1][j] > grid[i][j - 1]:
                        grid[i][j] = grid[i - 1][j]
                    else:
                        grid[i][j] = grid[i][j - 1]
        return grid[-1][-1][0]


class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        memo = [[-1] * (len(text2)+1) for _ in range(len(text1)+1)]
        return self.helper(text1, text2, 0, 0, memo)
    def helper(self, s1, s2, i, j, memo):
        if memo[i][j] != -1:
            return memo[i][j]
        if i == len(s1) or j == len(s2):
            return 0
        ans = 0
        if s1[i] == s2[j]:
            ans = 1 + self.helper(s1, s2, i+1, j+1, memo)
        else:
            ans = max(self.helper(s1, s2, i+1, j, memo), self.helper(s1, s2, i, j+1, memo))
        memo[i][j] = ans
        return ans
        
#     def longestCommonSubsequence(self, text1: str, text2: str) -> int:
#         m, n = len(text1), len(text2)
#         dp = [[0] * (n+1) for _ in range(m+1)]
#         for i in range(1, m+1):
#             for j in range(1, n+1):
#                 if text1[i-1] == text2[j-1]:
#                     dp[i][j] = 1 + dp[i-1][j-1]
#                 else:
#                     dp[i][j] = max(dp[i-1][j], dp[i][j-1])
                
#         return dp[-1][-1]


from functools import lru_cache
class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        
        
        @lru_cache(None)
        def lcs(idxA, idxB):
            if idxA < 0 or idxB < 0:
                return 0

            if text1[idxA] == text2[idxB]:
                return 1 + lcs(idxA - 1, idxB - 1)

            return max(lcs(idxA - 1, idxB), lcs(idxA, idxB - 1))

        return lcs(len(text1) - 1, len(text2) - 1)
            
            


class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        # If text1 doesn't reference the shortest string, swap them.
        if len(text2) < len(text1):
            text1, text2 = text2, text1
        
        
        # The previous column starts with all 0's and like before is 1
        # more than the length of the first word.
        previous = [0] * (len(text1) + 1)
        # Create a new array to represent the current column.
        current = [0] * (len(text1) + 1)
        
        # Iterate up each column, starting from the last one.
        for col in reversed(range(len(text2))):
            for row in reversed(range(len(text1))):
                if text2[col] == text1[row]:
                    current[row] = 1 + previous[row + 1]
                else:
                    current[row] = max(previous[row], current[row + 1])
            # The current column becomes the previous one.
            previous, current = current, previous
        
        # The original problem's answer is in previous[0]. Return it.
        return previous[0]
        
        '''
        # Make a grid of 0's with len(text2) + 1 columns 
        # and len(text1) + 1 rows.
        dp_grid = [[0] * (len(text2) + 1) for _ in range(len(text1) + 1)]
        
        # Iterate up each column, starting from the last one.
        for col in reversed(range(len(text2))):
            for row in reversed(range(len(text1))):
                # If the corresponding characters for this cell are the same...
                if text2[col] == text1[row]:
                    dp_grid[row][col] = 1 + dp_grid[row + 1][col + 1]
                # Otherwise they must be different...
                else:
                    dp_grid[row][col] = max(dp_grid[row + 1][col], dp_grid[row][col + 1])
        
        # The original problem's answer is in dp_grid[0][0]. Return it.
        return dp_grid[0][0]
        '''
        
        '''
        from functools import lru_cache
        @lru_cache(maxsize=None)
        def memo_solve(p1, p2):
            
            # Base case: If either string is now empty, we can't match
            # up anymore characters.
            if p1 == len(text1) or p2 == len(text2):
                return 0
            
            # Recursive case 1.
            if text1[p1] == text2[p2]:
                return 1 + memo_solve(p1 + 1, p2 + 1)
            
            # Recursive case 2.
            else:
                return max(memo_solve(p1, p2 + 1), memo_solve(p1 + 1, p2))
            
        return memo_solve(0, 0)
        '''
        
        
        '''
        def memo_solve(p1, p2):
            
            # Base case: If either string is now empty, we can't match
            # up anymore characters.
            if p1 == len(text1) or p2 == len(text2):
                return 0
            
            # Option 1: We don't include text1[p1] in the solution.
            option_1 = memo_solve(p1 + 1, p2)
            
            # Option 2: We include text1[p1] in the solution, as long as
            # a match for it in text2 at or after p2 exists.
            first_occurence = text2.find(text1[p1], p2)
            option_2 = 0
            if first_occurence != -1:
                option_2 = 1 + memo_solve(p1 + 1, first_occurence + 1)
            
            # Return the best option.
            return max(option_1, option_2)
                
        return memo_solve(0, 0)'''

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        rows = len(text1)
        cols = len(text2)
        
        dp = [[0 for j in range(cols)] for i in range(rows)]
        if text1[rows-1] == text2[cols-1]:
            dp[rows-1][cols-1] = 1
        for i in range(rows-1, -1, -1):
            for j in range(cols-1, -1, -1):
                if i == rows - 1 and j == cols-1:
                    continue
                right = 0
                down = 0
                rightdown = 0
                if i < rows - 1:
                    down = dp[i+1][j]
                if j < cols - 1:
                    right = dp[i][j+1]
                if i < rows - 1 and j < cols - 1:
                    rightdown = dp[i+1][j+1]
                if text1[i] == text2[j]:
                    dp[i][j] = 1 + rightdown
                else:
                    dp[i][j] = max(down, right)
        return dp[0][0]

class Solution:
    def longestCommonSubsequence(self, a: str, b: str) -> int:
        n1, n2 = len(a), len(b)
        memo = [[None] * (n2+1) for i in range(n1+1)]
        def helper(i, j):
            if memo[i][j] == None:
                if i == n1 or j == n2:
                    memo[i][j] = 0

                elif a[i] == b[j]:
                    return 1 + helper(i+1, j+1)
                else:
                    memo[i][j] = max(helper(i, j+1), helper(i+1, j))
            return memo[i][j]

        return helper(0, 0)

from collections import defaultdict
class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        # dp = defaultdict(lambda: -1)
        
        @lru_cache(maxsize = None)
        def helper(n, m):
            if m < 0 or n < 0:
                return 0
            # if dp[(m, n)] == -1:
            if text1[n] == text2[m]:
                length = 1 + helper(n-1, m-1)
            else:
                length = max(helper(n-1, m), 
                            helper(n, m-1))
                # dp[(m, n)] = length
            return length
        return helper(len(text1)-1, len(text2)-1)

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        import functools
        @functools.lru_cache(None)
        def helper(i,j):
            if i<0 or j<0:
                return 0
            if text1[i]==text2[j]:
                return helper(i-1,j-1)+1
            return max(helper(i-1,j),helper(i,j-1))
        return helper(len(text1)-1,len(text2)-1)
            


class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        m, n = len(text1), len(text2)
        
        @lru_cache(None)
        def find(i, j):
            if i >= m or j >= n:
                return 0
            if text1[i] == text2[j]:
                return 1+find(i+1, j+1)
            else:
                return max(find(i+1, j), find(i, j+1))
        
        return find(0, 0)
            


class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        rows = len(text1)
        cols = len(text2)
        
        dp = [[0 for j in range(cols)] for i in range(rows)]
        if text1[rows-1] == text2[cols-1]:
            dp[rows-1][cols-1] = 1
        for i in range(rows-1, -1, -1):
            for j in range(cols-1, -1, -1):
                if i == rows - 1 and j == cols-1:
                    continue
                print1 = False
                # if i == 2:
                #     print1 = True
                if print1:
                    print(i, j)
                right = 0
                down = 0
                rightdown = 0
                if i < rows - 1:
                    down = dp[i+1][j]
                if j < cols - 1:
                    right = dp[i][j+1]
                if i < rows - 1 and j < cols - 1:
                    rightdown = dp[i+1][j+1]
                # print(text1[i])
                # print(text2[j])
                # print(down)
                # print(right)
                if text1[i] == text2[j]:
                    dp[i][j] = 1 + rightdown
                else:
                    dp[i][j] = max(down, right)
        print(dp)
        return dp[0][0]

from functools import lru_cache
class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        
        @lru_cache(maxsize =None)
        def memo(l1,l2):
            if l1 == len(text1) or l2 == len(text2):
                return 0
            if text1[l1]==text2[l2]:
                return 1+ memo(l1+1,l2+1)
            else:
                return max(memo(l1+1,l2),memo(l1,l2+1))
        return memo(0,0)

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        
        @lru_cache(None)
        def recur(i, j):
            if i == -1 or j == -1:
                return 0
            
            if text1[i] == text2[j]:
                return recur(i-1, j-1) + 1
            else:
                return max(recur(i-1,j), recur(i, j -1))
            
        return recur(len(text1) - 1, len(text2) - 1)

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        # If text1 doesn't reference the shortest string, swap them.
        if len(text2) < len(text1):
            text1, text2 = text2, text1
        
        
        # The previous column starts with all 0's and like before is 1
        # more than the length of the first word.
        previous = [0] * (len(text1) + 1)
        
        # Iterate up each column, starting from the last one.
        for col in reversed(range(len(text2))):
            # Create a new array to represent the current column.
            current = [0] * (len(text1) + 1)
            for row in reversed(range(len(text1))):
                if text2[col] == text1[row]:
                    current[row] = 1 + previous[row + 1]
                else:
                    current[row] = max(previous[row], current[row + 1])
            # The current column becomes the previous one.
            previous = current
        
        # The original problem's answer is in previous[0]. Return it.
        return previous[0]
        
        '''
        # Make a grid of 0's with len(text2) + 1 columns 
        # and len(text1) + 1 rows.
        dp_grid = [[0] * (len(text2) + 1) for _ in range(len(text1) + 1)]
        
        # Iterate up each column, starting from the last one.
        for col in reversed(range(len(text2))):
            for row in reversed(range(len(text1))):
                # If the corresponding characters for this cell are the same...
                if text2[col] == text1[row]:
                    dp_grid[row][col] = 1 + dp_grid[row + 1][col + 1]
                # Otherwise they must be different...
                else:
                    dp_grid[row][col] = max(dp_grid[row + 1][col], dp_grid[row][col + 1])
        
        # The original problem's answer is in dp_grid[0][0]. Return it.
        return dp_grid[0][0]
        '''
        
        '''
        from functools import lru_cache
        @lru_cache(maxsize=None)
        def memo_solve(p1, p2):
            
            # Base case: If either string is now empty, we can't match
            # up anymore characters.
            if p1 == len(text1) or p2 == len(text2):
                return 0
            
            # Recursive case 1.
            if text1[p1] == text2[p2]:
                return 1 + memo_solve(p1 + 1, p2 + 1)
            
            # Recursive case 2.
            else:
                return max(memo_solve(p1, p2 + 1), memo_solve(p1 + 1, p2))
            
        return memo_solve(0, 0)
        '''
        
        
        '''
        def memo_solve(p1, p2):
            
            # Base case: If either string is now empty, we can't match
            # up anymore characters.
            if p1 == len(text1) or p2 == len(text2):
                return 0
            
            # Option 1: We don't include text1[p1] in the solution.
            option_1 = memo_solve(p1 + 1, p2)
            
            # Option 2: We include text1[p1] in the solution, as long as
            # a match for it in text2 at or after p2 exists.
            first_occurence = text2.find(text1[p1], p2)
            option_2 = 0
            if first_occurence != -1:
                option_2 = 1 + memo_solve(p1 + 1, first_occurence + 1)
            
            # Return the best option.
            return max(option_1, option_2)
                
        return memo_solve(0, 0)'''

from functools import lru_cache as memoize

class Solution():
    def longestCommonSubsequence(self, s1, s2):
        @memoize(None)
        def lcs(m,n):
            
            if(m==0 or n==0):
                return 0
            
            if s1[m-1] == s2[n-1]:
                return 1 + lcs(m-1,n-1)
            
            else:
                
                return max(lcs(m-1,n),lcs(m,n-1))
            
            
        return lcs(len(s1),len(s2))

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        from functools import lru_cache
        @lru_cache(maxsize=None)
        def memo_solve(p1, p2):
            
            # Base case: If either string is now empty, we can't match
            # up anymore characters.
            if p1 == len(text1) or p2 == len(text2):
                return 0
            
            # Recursive case 1.
            if text1[p1] == text2[p2]:
                return 1 + memo_solve(p1 + 1, p2 + 1)
            
            # Recursive case 2.
            else:
                return max(memo_solve(p1, p2 + 1), memo_solve(p1 + 1, p2))
            
        return memo_solve(0, 0)
        
        
        
        '''
        def memo_solve(p1, p2):
            
            # Base case: If either string is now empty, we can't match
            # up anymore characters.
            if p1 == len(text1) or p2 == len(text2):
                return 0
            
            # Option 1: We don't include text1[p1] in the solution.
            option_1 = memo_solve(p1 + 1, p2)
            
            # Option 2: We include text1[p1] in the solution, as long as
            # a match for it in text2 at or after p2 exists.
            first_occurence = text2.find(text1[p1], p2)
            option_2 = 0
            if first_occurence != -1:
                option_2 = 1 + memo_solve(p1 + 1, first_occurence + 1)
            
            # Return the best option.
            return max(option_1, option_2)
                
        return memo_solve(0, 0)'''

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        
        
        def lcs(text1,text2,m,n,dp):
            
            
            if m==0 or n==0:
                return 0
            
            if dp[m][n] !=-1:
                return dp[m][n]
            
            if text1[m-1] == text2[n-1]:
                dp[m][n] = 1 + lcs(text1,text2,m-1,n-1,dp)
                return dp[m][n]
            
            
            
            else:
                dp[m][n] = max(lcs(text1,text2,m,n-1,dp),lcs(text1,text2,m-1,n,dp))
                return dp[m][n]
            
         
        
        m = len(text1)
        
        n = len(text2)
        
        dp = [[-1 for i in range(n+1)] for j in range(m+1)]   

        res = lcs(text1,text2,m,n,dp)
  
    
        return res


from functools import lru_cache

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        
        @lru_cache(maxsize=None)
        def memo_solve(p1, p2):
            
            # Base case: If either string is now empty, we can't match
            # up anymore characters.
            if p1 == len(text1) or p2 == len(text2):
                return 0
            
            # Recursive case 1.
            if text1[p1] == text2[p2]:
                return 1 + memo_solve(p1 + 1, p2 + 1)
            
            # Recursive case 2.
            else:
                return max(memo_solve(p1, p2 + 1), memo_solve(p1 + 1, p2))
            
        return memo_solve(0, 0)

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        
        @lru_cache(maxsize = None)
        def memo_solve(index1, index2):
            
            if index1 == len(text1) or index2 == len(text2):
                return 0
            
            if text1[index1] == text2[index2]:
                return 1 + memo_solve(index1 + 1, index2 + 1)
            else:
                return max(memo_solve(index1, index2+1), memo_solve(index1+1, index2))
            
        return memo_solve(0,0)

from functools import lru_cache

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        
        @lru_cache(maxsize=None)
        def memo(i, j):
            if i == len(text1) or j == len(text2):
                return 0
            
            if text1[i] == text2[j]:
                return 1 + max(memo(i + 1, j + 1), memo(i + 1, j + 1))
            else:
                return max(memo(i + 1, j), memo(i, j + 1))
        
        return memo(0, 0)


class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        
        
        @lru_cache(maxsize=None)
        def helper(i, j):
            
            if i >= len(text1) or j >= len(text2):
                return 0
            
            elif text1[i] == text2[j]:
                return 1 + helper(i+1, j+1)
            
            l = helper(i + 1, j)
            r = helper(i, j + 1)
            
            return max(l, r)
                
        return helper(0, 0)
                
                


from functools import lru_cache

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        
        @lru_cache(maxsize=None)
        def memo_solve(p1, p2):
            
            # Base case: If either string is now empty, we can't match
            # up anymore characters.
            if p1 == len(text1) or p2 == len(text2):
                return 0
            
            if text1[p1] == text2[p2]:
                return 1 + memo_solve(p1+1, p2+1)
            else:
                return max(memo_solve(p1+1, p2),
                           memo_solve(p1, p2+1))
                
        return memo_solve(0, 0)

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        
        prev = [0] * (len(text2) + 1)
        curr = [0] * (len(text2) + 1)
        
        for row in range(len(text1)):
            for col in range(len(text2)):
                if text1[row] == text2[col]:
                    curr[col + 1] = 1 + prev[col]
                else:
                    curr[col + 1] = max(prev[col + 1], curr[col])
                    
            prev, curr = curr, prev
                    
        return prev[-1]

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
#         dp = [[0] * (len(text1) + 1) for _ in range(len(text2) + 1)]
        
#         # logic: if same, add 1, else max(try each without first)
#         # if row,col V == same, == prev diag + 1
#         # else: = max(row-1,col, row,col-1)
        
#         for row in range(1, len(text2) + 1):
#             for col in range(1, len(text1) + 1):
#                 if text2[row - 1] == text1[col - 1]:
#                     dp[row][col] = dp[row-1][col-1] + 1
#                 else:
#                     dp[row][col] = max(dp[row-1][col], dp[row][col-1])
        
#         return dp[-1][-1]
        from functools import lru_cache

        @lru_cache(maxsize=None)
        def lcs(i, j):
            if i == len(text1) or j == len(text2):
                return 0
            elif text1[i] ==  text2[j]:
                r = 1 + lcs(i + 1, j + 1)
            else:
                r = max(lcs(i + 1, j), lcs(i, j + 1))
                
            return r
        
        return lcs(0, 0)

class Solution:
    def longestCommonSubsequence(self, s1: str, s2: str) -> int:
        
        @lru_cache(None)
        def helper(i, j):
            if i == len(s1) or j == len(s2):
                return 0
            if s1[i] == s2[j]:
                return 1 + helper(i + 1, j + 1)
            else:
                return max(helper(i+1, j), helper(i, j + 1))
        return helper(0,0)


class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        
        @lru_cache(maxsize=None)
        def memo_solve(p1, p2):
            
            # Base case: If either string is now empty, we can't match
            # up anymore characters.
            if p1 == len(text1) or p2 == len(text2):
                return 0
            
            # Recursive case 1.
            if text1[p1] == text2[p2]:
                return 1 + memo_solve(p1 + 1, p2 + 1)
            
            # Recursive case 2.
            else:
                return max(memo_solve(p1, p2 + 1), memo_solve(p1 + 1, p2))
            
        return memo_solve(0, 0)

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        
        
        n = len(text1)
        m = len(text2)
        
        self.store = [[-1 for i in range(m)] for j in range(n)]
       
        self.Rec(text1,text2,n-1,m-1)
        
        return self.store[-1][-1]
    
    def Rec(self, text1, text2,n,m):
        
        
        if(n < 0 or m < 0):
            return 0
        
        if(self.store[n][m] != -1):
            return self.store[n][m]
        
        if(text1[n] == text2[m]):
            
            x = 1+self.Rec(text1,text2,n-1,m-1)
            
            self.store[n][m] = x
        
        else:
            x = max(self.Rec(text1,text2,n-1,m), self.Rec(text1,text2,n,m-1))
            
            self.store[n][m] = x
        
        return x

from functools import lru_cache
class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        
        @lru_cache(maxsize=None)
        def memo_solve(p1, p2):
            
            # Base case: If either string is now empty, we can't match
            # up anymore characters.
            if p1 == len(text1) or p2 == len(text2):
                return 0
            
            # Recursive case 1.
            if text1[p1] == text2[p2]:
                return 1 + memo_solve(p1 + 1, p2 + 1)
            
            # Recursive case 2.
            else:
                return max(memo_solve(p1, p2 + 1), memo_solve(p1 + 1, p2))
            
        return memo_solve(0, 0)

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        def lcs(i,j):
            if i==len(text1) or j==len(text2):
                return 0
            if dp[i][j]!=None:
                return dp[i][j]
            if text1[i]==text2[j]:
                dp[i][j]=1+lcs(i+1,j+1)
                return dp[i][j]
            dp[i][j]=max(lcs(i+1,j),lcs(i,j+1))
            return dp[i][j]
        dp=[[None for i in range(len(text2))] for j in range(len(text1))]
        # print(dp)
        # text1+=\"0\"
        # text2+=\"0\"
        lcs(0,0)
        return dp[0][0]

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        
#         h = {}
#         def longest(t1, t2):
#             if (t1, t2) in h:
#                 return h[(t1, t2)]
#             if not t1 or not t2:
#                 h[(t1, t2)] = 0
#                 return h[(t1, t2)]
#             elif t1[0] == t2[0]:
#                 h[(t1, t2)] = 1 + longest(t1[1:], t2[1:])
#                 return h[(t1, t2)]
#             else:
#                 h[(t1, t2)] = max(longest(t1, t2[1:]), longest(t1[1:], t2))
#                 return h[(t1, t2)]
            
#         return longest(text1, text2)

        @lru_cache(None)
        def longest(i, j):
            if i == len(text1) or j == len(text2):
                return 0
            elif text1[i] == text2[j]:
                return 1 + longest(i+1, j+1)
            else:
                return max(longest(i, j+1), longest(i+1, j))
        
        return longest(0, 0)

from functools import lru_cache as memoize

class Solution():
    def longestCommonSubsequence(self, text1, text2):
        @memoize(None)
        def lcs(s1,s2,m,n):
            
            if(m==0 or n==0):
                return 0
            
            if s1[m-1] == s2[n-1]:
                return 1 + lcs(s1,s2,m-1,n-1)
            
            else:
                
                return max(lcs(s1,s2,m-1,n),lcs(s1,s2,m,n-1))
            
            
        return lcs(text1,text2,len(text1),len(text2))

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        # if len(text2)>len(tex)
        
        memorize = [[-1] * (len(text2)+1) for _ in range(len(text1)+1)]
        def LCS(i1, i2):
            if i1 >= len(text1) or i2 >= len(text2): return 0
            if memorize[i1][i2]!=-1: return memorize[i1][i2]
            
            if text1[i1] == text2[i2]:
                memorize[i1][i2] = 1 + LCS(i1+1, i2+1)
            else:
                memorize[i1][i2] = max(LCS(i1,i2+1), LCS(i1+1,i2))
            return memorize[i1][i2]
        
        ans = LCS(0,0)
        return ans
#     def longestCommonSubsequence(self, text1: str, text2: str) -> int:
#         # if len(text2)>len(tex)
        
#         memorize = [[-1] * (len(text2)+1) for _ in range(len(text1)+1)]
#         def LCS(i1, i2):
#             if i1 >= len(text1) or i2 >= len(text2): return 0
            
#             if memorize[i1+1][i2]==-1:
#                 memorize[i1+1][i2] = LCS(i1+1, i2)  
#             option1 = memorize[i1+1][i2]
            
            
#             first_occurence = text2.find(text1[i1], i2)
            
#             if first_occurence != -1:
#                 if memorize[i1+1][i2+1]==-1:
#                     memorize[i1+1][first_occurence+1] = LCS(i1+1, first_occurence+1)
#                 option2 = 1 + memorize[i1+1][first_occurence+1]
#             else: option2 = 0
            
            
#             return max(option1, option2)
#         ans = LCS(0,0)
#         return ans
            


from functools import lru_cache

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        
        @lru_cache(maxsize=None)
        def memo_solve(p1,p2):
            n = len(text1)
            m = len(text2)
            if n==p1 or m==p2:
                return 0

            # case1 = memo_solve(p1+1,p2)
            # index = text2.find(text1[p1],p2)
            # if index !=-1:
            #     case2 = 1+memo_solve(p1+1,index+1)
            # else:
            #     case2 = 0
            
            if text1[p1]==text2[p2]:
                return 1 + memo_solve(p1+1,p2+1)

            return max(memo_solve(p1+1,p2),memo_solve(p1,p2+1))
        return memo_solve(0,0)


from typing import List


class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:

        # dp[i][j] 表示 text1[0:i+1] 和 text2[0:j+1] 的 Longest Common Subsequence 的长度
        # 其中 0 <= i < len(text1)
        # 其中 0 <= j < len(text2)
        dp: List[List[int]] = []
        for i in range(len(text1)):
            dp.append(len(text2) * [-1])

        def cal_with_cache(i: int, j: int):
            if i < 0 or j < 0:
                return 0

            if dp[i][j] == -1:
                dp[i][j] = cal(i, j)
            return dp[i][j]

        def cal(i: int, j: int):
            if i == 0 and j == 0:
                return 1 if text1[i] == text2[j] else 0

            if text1[i] == text2[j]:
                return cal_with_cache(i - 1, j - 1) + 1
            else:
                return max(cal_with_cache(i - 1, j), cal_with_cache(i, j - 1))

        return cal_with_cache(len(text1) - 1, len(text2) - 1)



class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        
        dp = defaultdict(int)
        for i, c1 in enumerate(text1):
            for j, c2 in enumerate(text2):
                dp[i,j]  = max(dp[i-1, j-1] + (c1==c2), dp[i-1,j], dp[i,j-1])
                
        return dp[len(text1)-1, len(text2)-1]

from functools import lru_cache
class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        @lru_cache(None)
        def dp(i,j,strx,stry):
            if i>=len(strx) or j>=len(stry):
                return 0
            elif strx[i]==stry[j]:
                return 1+dp(i+1,j+1,strx,stry)
            else:
                return max(dp(i,j+1,strx,stry),dp(i+1,j,strx,stry))
        return dp(0,0,text1,text2)




class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        m, n = len(text1), len(text2)
        memo = [[-1 for _ in range(n)] for _ in range(m)]
        return self.lcs(text1, 0, text2, 0, memo)
    
    def lcs(self, t1, i, t2, j, memo):
        if i >= len(t1) or j >= len(t2): return 0
        elif memo[i][j] != -1: return memo[i][j]
        else:
            result = -1
            if t1[i] == t2[j]:
                result = 1 + self.lcs(t1, i+1, t2, j+1, memo)
            else:
                result = max(self.lcs(t1, i+1, t2, j, memo), self.lcs(t1, i, t2, j+1, memo))
            memo[i][j] = result
            return result

class Solution:
    def longestCommonSubsequence(self, s1: str, s2: str) -> int:
        
        @lru_cache(None)
        def helper(s1, s2, i, j):
            if i == len(s1) or j == len(s2):
                return 0
            if s1[i] == s2[j]:
                return 1 + helper(s1, s2, i + 1, j + 1)
            else:
                return max(helper(s1, s2, i+1, j), helper(s1, s2, i, j + 1))
        return helper(s1,s2,0,0)


from functools import lru_cache

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        if len(text1) == 0 or len(text2) == 0:
            return 0
        
        t1_idx = len(text1) - 1
        t2_idx = len(text2) - 1
        
        @lru_cache(maxsize=2147483647)
        def lcs(t1_idx, t2_idx):
            if t1_idx == -1 or t2_idx == -1:
                return 0
            if text1[t1_idx] == text2[t2_idx]:
                return 1 + lcs(t1_idx - 1, t2_idx - 1)
            else:
                return max(lcs(t1_idx, t2_idx - 1), lcs(t1_idx - 1, t2_idx))
        
        return lcs(t1_idx, t2_idx)

class Solution:
    # def longestCommonSubsequence(self, text1: str, text2: str) -> int:
    #     matrix = [[None]*(len(text2)+1) for i in range(len(text1)+1)]
    #     for j in range(len(text2)+1):
    #         matrix[0][j] = 0
    #     for i in range(len(text1)+1):
    #         matrix[i][0] = 0
    #     for i in range(1, len(text1)+1):
    #         for j in range(1, len(text2)+1):
    #             if text1[i-1] == text2[j-1]:
    #                 matrix[i][j] = 1 + matrix[i-1][j-1]
    #             else:
    #                 matrix[i][j] = max(matrix[i-1][j], matrix[i][j-1])
    #     return matrix[len(text1)][len(text2)]
    
    
    
    
    
    

    
    
    


    def longestCommonSubsequence(self, s1, s2):
        def _longest_common_subsequence(i, j, cache):
            p = (i, j)
            if p in cache:
                return cache[p]
            elif i < 0 or j < 0:
                return 0
            elif s1[i] == s2[j]:
                answer = 1 + _longest_common_subsequence(i-1, j-1, cache)
                cache[p] = answer
                return answer
            else:
                answer = max(_longest_common_subsequence(i, j-1, cache), _longest_common_subsequence(i-1, j, cache))
                cache[p] = answer
                return answer
        return _longest_common_subsequence(len(s1)-1, len(s2)-1, {})

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        memo = [[ -1 for i in range(len(text2))] for i in range (len(text1))]
        
        def memoSolve(i, j) :
            if i == len(text1) or j == len(text2):
                return 0
            
            if memo[i][j] >= 0:
                return memo[i][j]
            
            answer = 0
            if text1[i] == text2[j]:
                answer = 1+ memoSolve(i+1, j+1)
            else:
                answer = max(memoSolve(i+1,j), memoSolve(i,j+1))
            memo[i][j] = answer
            return memo[i][j]
            
        return memoSolve(0,0)

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        if not text1 or not text2: return 0
        mem1 = [0] * (len(text2) + 1)
        mem2 = [0] * (len(text2) + 1)
        for i in range(len(text1)):
            for j in range(len(text2)):
                if text1[i] == text2[j]:
                    mem2[j+1] = mem1[j] + 1
                else:
                    mem2[j+1] = max(mem2[j], mem1[j+1])
            mem1 = mem2
            mem2 = [0] * (len(text2) + 1)
        return mem1[-1]

        
        
        
        
        


class Solution:
    def __init__(self):
        self.dp = None
        
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        self.dp = [[-1] * (len(text2) + 1) for _ in range(len(text1) + 1)]
        return self.lcs_rec(text1, text2, len(text1), len(text2))
        
    def lcs_rec(self, x, y, n, m):
        # Base Condition
        if n == 0 or m == 0:
            return 0
        
        # Memoization
        if self.dp[n][m] != -1:
            return self.dp[n][m]
        
        # Choice for subsequence
        if x[n - 1] == y[m - 1]:
            self.dp[n][m] = 1 + self.lcs_rec(x, y , n - 1, m - 1)
        else:
            self.dp[n][m] =  max(self.lcs_rec(x, y, n - 1, m), self.lcs_rec(x, y, n, m - 1))
        return self.dp[n][m]

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        def s(i, j, cache):
            p = (i,j)
            if p not in cache:
                if text1[i] == text2[j]:
                    cache[p] = 1 + s(i-1, j-1, cache)
                else:
                    cache[p] = max(s(i, j-1, cache), s(i-1, j, cache))
            return cache[p]
        cache = {(-1, i): 0 for i in range(len(text2))}
        for i in range(len(text1)):
            cache[(i, -1)] = 0
        cache[(-1, -1)] = 0
        return s(len(text1)-1, len(text2)-1, cache)

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        @lru_cache(None)
        def dfs(i, j):
            if i < 0 or j < 0: return 0
            if text1[i] == text2[j]: return 1+dfs(i-1, j-1)
            return max(dfs(i, j-1), dfs(i-1, j))
        
        if not(text1 and text2): return 0
        n, m = len(text1), len(text2)
        return dfs(n-1, m-1)


class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        dp = [[0 for i in range(len(text2))] for j in range(len(text1))]
        
        for i in range(len(text1)):
            for j in range(len(text2)):
                if text1[i] == text2[j]:
                    dp[i][j] = (dp[i-1][j-1] if i>0 and j>0 else 0) + 1
                else:
                    p1 = dp[i-1][j] if i >0 else 0
                    p2 = dp[i][j-1] if j > 0 else 0
                    p3 = dp[i-1][j-1] if i>0 and j>0 else 0
                    max_num = max(p1,p2,p3)
                    dp[i][j] = max_num
        return dp[-1][-1]

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        if not text1 or not text2:
            return 0
        

        cacheRow = [None] * len(text2)
        cache = [cacheRow[:] for i in range(len(text1))]
        return self.dp(text1, text2, 0, 0, cache)
        
    
    def dp(self, text1, text2, i, j, cache):
        if i >= len(text1) or j >= len(text2):
            return 0
        
        if cache[i][j] is None:
            if text1[i] == text2[j]:
                cache[i][j] = 1 + self.dp(text1, text2, i+1, j+1, cache)
            else:
                cache[i][j] = max(self.dp(text1, text2, i+1, j, cache), self.dp(text1, text2, i, j+1, cache))
        
        return cache[i][j]

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        def s(i, j):
            p = (i,j)
            if p not in cache:
                if text1[i] == text2[j]:
                    cache[p] = 1 + s(i-1, j-1)
                else:
                    cache[p] = max(s(i, j-1), s(i-1, j))
            return cache[p]
        cache = {(-1, i): 0 for i in range(len(text2))}
        for i in range(len(text1)):
            cache[(i, -1)] = 0
        cache[(-1, -1)] = 0
        return s(len(text1)-1, len(text2)-1)

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        if not text1 or not text2:
            return 0
        n1 = len(text1)
        n2 = len(text2)
        dp = [[0 for _ in range(n2 + 1)] for _ in range(2)]
        
        for i in range(n1 + 1):
            for j in range(n2 + 1):
                if i == 0 or j == 0:
                    dp[i % 2][j] = 0
                else:
                    if text1[i - 1] == text2[j - 1]:
                        dp[i % 2][j] = dp[1 - i % 2][j - 1] + 1
                    else:
                        dp[i % 2][j] = max(dp[1 - i % 2][j], dp[i % 2][j - 1])
        return dp[n1 % 2][n2]


class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        
        # Create dp 2D array
        dp = [[-1] * (len(text2)) for _ in range(len(text1))]

        # Recursive helper function
        def lcsForCell(i, j):
            # Boundary conditions
            if (i < 0) or (j < 0):
                return 0

            if dp[i][j] != -1:
                return dp[i][j]

            # If letters are the same
            if text1[i] == text2[j]:
                dp[i][j] = lcsForCell(i-1, j-1) + 1

            else:
                dp[i][j] = max(lcsForCell(i-1, j), lcsForCell(i, j-1))

            return dp[i][j]
        
        return lcsForCell(len(text1)-1, len(text2)-1)
        
                


class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        if len(text1) < len(text2):
            text1, text2 = text2, text1
        
        prev = [0] * (len(text2) + 1)
        curr = [0] * (len(text2) + 1)
        
        for row in range(len(text1)):
            for col in range(len(text2)):
                if text1[row] == text2[col]:
                    curr[col + 1] = 1 + prev[col]
                else:
                    curr[col + 1] = max(prev[col + 1], curr[col])
                    
            prev, curr = curr, prev
                    
        return prev[-1]

'''
The subproblem here is: suffixes

\"abcde\"
\"ce\"

So becase first letter \"a\" is in both text, its 1 plus the lcs of \"bcde\" and \"ace\"

if its not the same however, we try take suffix of both and see which one matches, we return longest 


'''
class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        n1 = len(text1)
        n2 = len(text2)
        
        memo = {}
        def lcs(pointer1, pointer2):
            if (pointer1, pointer2) in memo: return memo[(pointer1, pointer2)]
            if pointer1 >= n1 or pointer2 >= n2: return 0
            if text1[pointer1] == text2[pointer2]:
                # move on to the next
                x =  1 + lcs(pointer1 + 1, pointer2 + 1)
            else:
                x =  max(lcs(pointer1 + 1, pointer2), lcs(pointer1, pointer2+1))
            memo[(pointer1, pointer2)] = x
            return x
            
            
        return lcs(0,0)
            
            
            


class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        '''
        f[i][j]: 前i个，前j个匹配的最长
        '''
        m, n = len(text1), len(text2)
        f = [[0] * (n+1) for _ in range(m+1)]
        for i in range(m+1):
            for j in range(n+1):
                if i == 0 and j == 0:
                    f[i][j] = 0
                elif i == 0:
                    f[i][j] = 0
                elif j == 0:
                    f[i][j] = 0
                else:
                    if text1[i-1] == text2[j-1]:
                        f[i][j] = max(f[i][j-1], f[i-1][j], f[i-1][j-1] + 1)
                    else:     
                        f[i][j] = max(f[i][j-1], f[i-1][j])
                        
        return f[m][n]

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        def solve(i, j):
            # Base case: reached end of one of the strings
            if i == n or j == m:
                return 0
            
            # Memoization case
            if memo[i][j] != -1:
                return memo[i][j]
            
            # Recursive case 1: text1[i] == text2[j]
            if text1[i] == text2[j]:
                memo[i][j] = 1 + solve(i+1, j+1)
                
            # Recursive case 2: text1[i] != text2[j]
            else:
                memo[i][j] = max(solve(i, j+1), solve(i+1, j))
            
            return memo[i][j]
        
        n, m = len(text1), len(text2)
        
        memo = [[-1 for _ in range(m)] for _ in range(n)]
        
        return solve(0, 0)
            


class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        memo = [[-1] * (len(text2) + 1) for _ in range(len(text1) + 1)]
        def dfs(t1, t2):
            n1, n2 = len(t1), len(t2)
            if memo[n1][n2] != -1:
                return memo[n1][n2]
            if n1 == 0 or n2 == 0:
                return 0
            
            if t1[-1] == t2[-1]:
                res = dfs(t1[:-1], t2[:-1]) + 1
            else:
                res = max(dfs(t1[:-1], t2), dfs(t1, t2[:-1]))
            memo[n1][n2] = res
            return res
        dfs(text1, text2)
        return memo[-1][-1]

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        def s(i, j, cache):
            p = (i,j)
            if p not in cache:
                c = 0
                while i >= 0 and j >= 0 and text1[i] == text2[j]:
                    c += 1
                    i -= 1
                    j -= 1
                if c > 0:
                    cache[p] = c + s(i, j, cache)
                else:
                    cache[p] = max(s(i, j-1, cache), s(i-1, j, cache))
            return cache[p]
        cache = {(-1, i): 0 for i in range(len(text2))}
        for i in range(len(text1)):
            cache[(i, -1)] = 0
        cache[(-1, -1)] = 0
        return s(len(text1)-1, len(text2)-1, cache)

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        self.n = len(text1)
        self.m = len(text2)
        self.text1 = text1
        self.text2 = text2
        self.table = []
        for i in range(self.n):
            self.table.append([-1] * self.m)
        return self.longest(0,0)
            
    def longest(self, i, j):
        if (i == self.n) or (j == self.m):
            return 0
        if self.table[i][j] != -1:
            return self.table[i][j]
        else:
            if self.text1[i] == self.text2[j]:
                self.table[i][j] = 1 + self.longest(i+1, j+1)
            else:
                self.table[i][j] = max(self.longest(i+1, j), self.longest(i, j+1))
            return self.table[i][j]
            


from functools import lru_cache

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        
#         @lru_cache(maxsize=None)
#         def recur(n,m):
            
#             if n == len(text1) or m == len(text2):
#                 return 0
            
#             if text1[n] == text2[m]:
#                 return 1 + recur(n+1,m+1)
            
#             else:
            
#                 return max(recur(n,m+1),recur(n+1,m))
                
        
#         return recur(0,0)
        
    #    '' a b c d e
    # '' 0  0 0 0 0 0 
    # a  0  1 1 1 1 1
    # c  0  1 1 2 2 2
    # e  0  1 1 2 2 3
    
        # dp = [[0]*(len(text1)+1) for _ in range(len(text2)+1)]
        
        previous = [0] * (len(text1) + 1)
        current = [0] * (len(text1) + 1)
        # print(len(dp),len(dp[0]))
        
        for i in range(1,len(text2)+1):
            for j in range(1,len(text1)+1):
                
                if text2[i-1] == text1[j-1]:
                    
                    current[j] = previous[j-1] + 1
                else:
                    current[j] = max(current[j-1], previous[j])
                
            previous = current
            current = [0] * (len(text1) + 1)
                
        return previous[-1]









#         dp_grid = [[0]*(len(text1)+1) for _ in range(len(text2)+1)]
      
#         for row in range(len(text2)):
#             for col in range(len(text1)):
#                 # print(row,col)
#                 if text1[col] == text2[row]:
#                     dp_grid[row+1][col+1] = 1 + dp_grid[row][col]
#                 else:
#                     dp_grid[row+1][col+1] = max(dp_grid[row][col+1],dp_grid[row+1][col])
        
#         return dp_grid[len(text2)][len(text1)]
                    


class Solution:
    def longestCommonSubsequence(self, s1: str, s2: str) -> int:
      dp = [[0] * (len(s2) + 1) for _ in range(len(s1) + 1)]

      # s1: row
      # s2: col
      for s1_index in range(len(s1)):
        for s2_index in range(len(s2)):
          if s1[s1_index] != s2[s2_index]:
            dp[s1_index + 1][s2_index + 1] = max(dp[s1_index][s2_index + 1],
                                                 dp[s1_index + 1][s2_index],
                                                 dp[s1_index][s2_index])
          else:
            dp[s1_index + 1][s2_index + 1] = max(dp[s1_index][s2_index + 1],
                                                 dp[s1_index + 1][s2_index],
                                                 dp[s1_index][s2_index] + 1)
      return dp[-1][-1]

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        @lru_cache(maxsize=None)
        def memo_solve(p1, p2):
            
            # Base case: If either string is now empty, we can't match
            # up anymore characters.
            if p1 == len(text1) or p2 == len(text2):
                return 0
            
            # Option 1: We don't include text1[p1] in the solution.
            option_1 = memo_solve(p1 + 1, p2)
            
            # Option 2: We include text1[p1] in the solution, as long as
            # a match for it in text2 at or after p2 exists.
            first_occurence = text2.find(text1[p1], p2)
            option_2 = 0
            if first_occurence != -1:
                option_2 = 1 + memo_solve(p1 + 1, first_occurence + 1)
            
            # Return the best option.
            return max(option_1, option_2)
                
        return memo_solve(0, 0)

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        def s(i, j, cache):
            if i < 0 or j < 0:
                return 0
            p = (i,j)
            if p not in cache:
                if text1[i] == text2[j]:
                    cache[p] = 1 + s(i-1, j-1, cache)
                else:
                    cache[p] = max(s(i, j-1, cache), s(i-1, j, cache))
            return cache[p]
        cache = {}
        # cache = {(-1, i): 0 for i in range(len(text2))}
        # for i in range(len(text1)):
        #     cache[(i, -1)] = 0
        # cache[(-1, -1)] = 0
        return s(len(text1)-1, len(text2)-1, cache)

class Solution:
    def lcs(self, text1, text2, i1, i2, memo):
        if len(text1) == i1 or len(text2) == i2:
            return 0
        
        if memo[i1][i2] != -1:
            return memo[i1][i2]
        
        if text1[i1] == text2[i2]:
            memo[i1][i2] = 1 + self.lcs(text1, text2, i1 + 1, i2 + 1, memo)
            return memo[i1][i2]
        
        maxLen = 0
        maxLen = max(maxLen, self.lcs(text1, text2, i1 + 1, i2, memo))
        maxLen = max(maxLen, self.lcs(text1, text2, i1, i2 + 1, memo))
        memo[i1][i2] = maxLen
        
        return maxLen
        
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        memo = [[-1 for _ in range(len(text2))] for _ in range(len(text1))]
        maxLen = self.lcs(text1, text2, 0, 0, memo)
        return maxLen

class Solution:
    def lcs(self, s1, s2, m, n):
        if m == 0 or n == 0:
            return 0
        if self.dp[m][n] != -1: return self.dp[m][n]
        if s1[m - 1] == s2[n - 1]:
            self.dp[m][n] = 1 + self.lcs(s1, s2, m - 1, n - 1)
        else:
            self.dp[m][n] = max(self.lcs(s1, s2, m - 1, n), self.lcs(s1, s2, m, n - 1))
        return self.dp[m][n]

    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        m = len(text1)
        n = len(text2)
        self.dp = [[-1 for _ in range(n + 1)] for __ in range(m + 1)]
        return self.lcs(text1, text2, m, n)


class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        mem = {}
        def dfs(l, r):
            if((l, r) in mem):
                return mem[(l, r)]
            if(l == len(text1) or r == len(text2)):
                return 0
            ans = 0
            if(text1[l] == text2[r]):
                ans = 1+dfs(l+1, r+1)
            else:
                ans = max(dfs(l+1, r), dfs(l, r+1))
            mem[(l, r)] = ans
            return ans
        return dfs(0, 0)

'''
     text2 a c e
         0 1 2 3
text1 0  0 0 0 0
    a 1  0 1 1 1
    b 2  0 1 1 1
    c 3  0 1 2 2
    d 4  0 1 2 2
    e 5  0 1 2 3
'''

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        # dp[i][j] reprents the length of the longest common subsequence for text1[:i] and text2[:j]
        m, n = len(text1) + 1, len(text2) + 1
        dp = [[0] * n for _ in range(m)]
        res = 0
        for i in range(1, m):  # start from one char
            for j in range(1, n):
                if text1[i-1] == text2[j-1]:
                    dp[i][j] = dp[i-1][j-1] + 1
                else:
                    dp[i][j] = max(dp[i][j-1], dp[i-1][j])
                res = max(res, dp[i][j])                                                        
        return res

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
#         dp = [[0] * (len(text1) + 1) for _ in range(len(text2) + 1)]
        
#         # logic: if same, add 1, else max(try each without first)
#         # if row,col V == same, == prev diag + 1
#         # else: = max(row-1,col, row,col-1)
        
#         for row in range(1, len(text2) + 1):
#             for col in range(1, len(text1) + 1):
#                 if text2[row - 1] == text1[col - 1]:
#                     dp[row][col] = dp[row-1][col-1] + 1
#                 else:
#                     dp[row][col] = max(dp[row-1][col], dp[row][col-1])
        
#         return dp[-1][-1]
        from functools import lru_cache

        memo = {}
        def lcs(i, j):
            if (i, j) in memo:
                return memo[(i, j)]
            if i == len(text1) or j == len(text2):
                r = 0
            elif text1[i] ==  text2[j]:
                r = 1 + lcs(i + 1, j + 1)
            else:
                r = max(lcs(i + 1, j), lcs(i, j + 1))
                
            memo[(i, j)] = r
            return r
        
        return lcs(0, 0)

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        if len(text1) <= len(text2) :
            ss, ls = text1, text2
        else :
            ss, ls = text2, text1
        track = [0] * len(ss)
        
        
        for i2 in range(0, len(ls)) :
            prev = track[0]
            if ls[i2] == ss[0] :
                track[0] = 1
            for i1 in range(1, len(ss)) :
                newPrev = track[i1]
                if ls[i2] == ss[i1] :
                    track[i1] = prev + 1
                else :
                    track[i1] = max(track[i1], track[i1-1])
                prev = newPrev
        return track[-1]
                
            


class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        dp = {}
        
        def lcs(left, right):
            nonlocal text1
            nonlocal text2
            if (left, right) in dp:
                return dp[(left, right)]
            if left >= len(text1) or right >= len(text2):
                return 0
            if text1[left] == text2[right]:
                count = 1 + lcs(left + 1, right + 1)
                dp[(left, right)] = count
                return count
            else:
                count = max(lcs(left + 1, right), lcs(left, right + 1))
                dp[(left, right)] = count
                return count
        return lcs(0, 0)

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        memo = {}
        def dpRecurse(i : int, j : int):
            result = 0
            if (i, j) in memo:
                return memo[(i, j)]
            
            if i >= len(text1) or j >= len(text2):
                return 0;
            elif text1[i] == text2[j]:
                result = 1 + dpRecurse(i + 1, j + 1)
            else:
                result = max(dpRecurse(i + 1, j), dpRecurse(i, j + 1))
            memo[(i, j)] = result
            return result
            
        return dpRecurse(0, 0)


class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        from functools import lru_cache
        @lru_cache(maxsize=None)
        def memo_solve(p1, p2):
            
            # Base case: If either string is now empty, we can't match
            # up anymore characters.
            if p1 == len(text1) or p2 == len(text2):
                return 0
            
            # Option 1: We don't include text1[p1] in the solution.
            option_1 = memo_solve(p1 + 1, p2)
            
            # Option 2: We include text1[p1] in the solution, as long as
            # a match for it in text2 at or after p2 exists.
            first_occurence = text2.find(text1[p1], p2)
            option_2 = 0
            if first_occurence != -1:
                option_2 = 1 + memo_solve(p1 + 1, first_occurence + 1)
            
            # Return the best option.
            return max(option_1, option_2)
                
        return memo_solve(0, 0)

from functools import lru_cache

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        
        @lru_cache(maxsize=None)
        def memo_solve(p1, p2):
            
            # Base case: If either string is now empty, we can't match
            # up anymore characters.
            if p1 == len(text1) or p2 == len(text2):
                return 0
            
            # Option 1: We don't include text1[p1] in the solution.
            option_1 = memo_solve(p1 + 1, p2)
            
            # Option 2: We include text1[p1] in the solution, as long as
            # a match for it in text2 at or after p2 exists.
            first_occurence = text2.find(text1[p1], p2)
            option_2 = 0
            if first_occurence != -1:
                option_2 = 1 + memo_solve(p1 + 1, first_occurence + 1)
            
            # Return the best option.
            return max(option_1, option_2)
                
        return memo_solve(0, 0)

from functools import lru_cache


class Solution:
    def longestCommonSubsequence(self, txt1: str, txt2: str) -> int:
        @lru_cache(maxsize=None)
        def rec(i, j):
            if i == -1 or j == -1:
                return 0
            if txt1[i] == txt2[j]:
                return rec(i-1, j-1) + 1
            if txt1[i] != txt2[j]:
                return max(rec(i-1, j), rec(i, j-1))
            
        return rec(len(txt1) - 1, len(txt2) - 1)


class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        memo = {}
        def dpRecurse(i : int, j : int):
            result = 0
            if (i, j) in memo:
                return memo[(i, j)]
            
            if i >= len(text1) or j >= len(text2):
                return 0;
            elif text1[i] == text2[j]:
                result = 1 + dpRecurse(i + 1, j + 1)
            else:
                result = max(dpRecurse(i + 1, j), dpRecurse(i, j + 1))
            memo[(i, j)] = result
            return result
            
        return dpRecurse(0, 0)

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        return self.lcs(text1, text2, len(text1) - 1, len(text2) - 1, {})

    def lcs(self, text1, text2, i, j, memo):
        if i < 0 or j < 0:
            return 0
        
        if (i, j) in memo:
            return memo[(i, j)]

        if text1[i] == text2[j]:
            return 1 + self.lcs(text1, text2, i - 1, j - 1, memo)
        
        memo[(i, j)] = max(
            self.lcs(text1, text2, i - 1, j, memo),
            self.lcs(text1, text2, i, j - 1, memo),
        )
        
        return memo[(i, j)]

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        return self.find({}, 0, 0, text1, text2)
    def find(self, memo, i, j, text1, text2):
        if (i, j) in memo:
            return memo[(i, j)]
        if i == len(text1):
            return 0
        if j == len(text2):
            return 0
        if text1[i] == text2[j]:
            memo[(i, j)] = self.find(memo, i+1, j+1, text1, text2) + 1
        else:
            memo[(i, j)] = max(self.find(memo, i, j+1, text1, text2), self.find(memo, i+1, j, text1, text2))
        return memo[(i, j)]

from functools import lru_cache


class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        @lru_cache(maxsize=None)
        def rec(txt1, txt2, len1, len2):

            if len1 == 0 or len2 == 0:
                return 0
            if txt1[len1-1] == txt2[len2-1]:
                return rec(txt1, txt2, len1-1, len2-1) + 1
            else:
                return max(rec(txt1, txt2, len1-1, len2), rec(txt1, txt2, len1, len2-1))
        return rec(text1, text2, len(text1), len(text2))


import math

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        m = len(text1)
        n = len(text2)
        
        if m == 0 or n == 0:
            return 0
        
        mat = [[-math.inf]*(n+1) for _ in range(m+1)]
        prev = [0]*(n+1)
        curr = [0] + [-math.inf]*n
            
        for a in range(1, m+1):
            for b in range(1, n + 1):
                if text1[a-1] == text2[b-1]:
                    curr[b] = 1 + prev[b-1]
                else:
                    curr[b] = max(curr[b-1], prev[b])
            
            prev = curr
            curr = [0] + [-math.inf]*n
        
        return prev[n]


class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        memo = {}
        return self.helper(0,0,text1,text2,memo)
        
    def helper(self,index_1,index_2,text1,text2,memo):
        if (index_1 == len(text1) or index_2 == len(text2)):
            return 0
        elif (index_1,index_2) in memo:
            return memo[(index_1,index_2)]
        else:
            if (text1[index_1] == text2[index_2]):
                ans = 1 + self.helper(index_1 + 1,index_2 + 1,text1,text2,memo)
            else:
                ans = max(self.helper(index_1 + 1,index_2,text1,text2,memo),
                          self.helper(index_1,index_2 + 1,text1,text2,memo))
            memo[(index_1,index_2)] = ans
            return ans


class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        hist = {}
        
        def helper(str1, str2, m, n):
            if (m, n) in hist:
                return hist[(m, n)]
            
            if m == 0 or n == 0:
                return 0
            elif str1[m-1] == str2[n-1]:
                hist[(m, n)] = 1 + helper(str1, str2, m-1, n-1)
                return hist[(m, n)] 
            
            hist[(m, n)] = max(
                helper(str1, str2, m-1, n),
                helper(str1, str2, m, n-1)
            )
            return hist[(m, n)]
        return helper(text1, text2, len(text1), len(text2))

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        def _longest_common_subsequence(i, j):
            if i < 0 or j < 0:
                return 0
            
            if (i, j) not in mem:
                if text1[i] != text2[j]:
                    mem[(i, j)] = max(_longest_common_subsequence(i - 1, j), _longest_common_subsequence(i, j - 1))
                else:
                    mem[(i, j)] = _longest_common_subsequence(i - 1, j - 1) + 1
            
            return mem[(i, j)]
        
        mem = {}
        return _longest_common_subsequence(len(text1) - 1, len(text2) - 1)


from typing import List


class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:

        # dp[i][j] 表示 text1[0:i+1] 和 text2[0:j+1] 的 Longest Common Subsequence 的长度
        # 其中 0 <= i < len(text1)
        # 其中 0 <= j < len(text2)
        dp: List[List[int]] = []
        for i in range(len(text1)):
            dp.append(len(text2) * [-1])

        def cal_with_cache(i: int, j: int):
            if i < 0 or j < 0:
                return 0

            if dp[i][j] == -1:
                dp[i][j] = cal(i, j)
            return dp[i][j]

        def cal(i: int, j: int):
            if i == 0 and j == 0:
                return 1 if text1[i] == text2[j] else 0

            if text1[i] == text2[j]:
                return cal_with_cache(i - 1, j - 1) + 1
            else:
                return max(cal_with_cache(i - 1, j), cal_with_cache(i, j - 1))

        for i in range(len(text1)):
            for j in range(len(text2)):
                cal_with_cache(i, j)

        return cal_with_cache(len(text1) - 1, len(text2) - 1)



import numpy as np
class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        
        l1 = len(text1)
        l2 = len(text2)
        
        dp = np.zeros((l1+1, l2+1), dtype = int)
        
    
        dp[:][0] = 0
        
  
        dp[0][:] = 0
            
        for i in range(1, l1+1):
            for j in range(1, l2+1):
                if text1[i-1] == text2[j-1]:
                    dp[i][j] = 1 + dp[i-1][j-1]
                else:
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])
                    
        return dp[-1][-1]
        
        


class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        memo = {}
        if not text1 or not text2:
            return 0
        def lcs(i,j):
            if i == len(text1) or j == len(text2):
                return 0
            if (i,j) in memo:
                return memo[(i,j)]
            
            if text1[i] == text2[j]:
                ans = 1 + lcs(i+1,j+1)
            else:
                ans = max(lcs(i+1,j), lcs(i,j+1))
            memo[(i,j)] = ans
            return ans
        
        return lcs(0,0)

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
#         dp = [[0] * (len(text1) + 1) for _ in range(len(text2) + 1)]
        
#         # logic: if same, add 1, else max(try each without first)
#         # if row,col V == same, == prev diag + 1
#         # else: = max(row-1,col, row,col-1)
        
#         for row in range(1, len(text2) + 1):
#             for col in range(1, len(text1) + 1):
#                 if text2[row - 1] == text1[col - 1]:
#                     dp[row][col] = dp[row-1][col-1] + 1
#                 else:
#                     dp[row][col] = max(dp[row-1][col], dp[row][col-1])
        
#         return dp[-1][-1]
        from functools import lru_cache

        memo = {}
        def lcs(i, j):
            if i == len(text1) or j == len(text2):
                return 0
            if (i, j) in memo:
                return memo[(i, j)]
            elif text1[i] ==  text2[j]:
                r = 1 + lcs(i + 1, j + 1)
            else:
                r = max(lcs(i + 1, j), lcs(i, j + 1))
                
            memo[(i, j)] = r
            return r
        
        return lcs(0, 0)

import numpy as np
class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        
        l1 = len(text1)
        l2 = len(text2)
        
        dp = np.zeros((l1+1, l2+1), dtype = int)
        
        for i in range(l1+1):
            dp[i][0] = 0
        
        for i in range(l2+1):
            dp[0][i] = 0
            
        for i in range(1, l1+1):
            for j in range(1, l2+1):
                if text1[i-1] == text2[j-1]:
                    dp[i][j] = 1 + dp[i-1][j-1]
                else:
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])
                    
        return dp[-1][-1]
        
        


class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        memo = [[ -1 for i in range(len(text2))] for i in range (len(text1))]
        
        def memoSolve(i, j) :
            if i == len(text1) or j == len(text2):
                return 0
            
            if memo[i][j] >= 0:
                return memo[i][j]
            
            include = 0
            j2 = text2.find(text1[i], j)
            if j2 != -1:
                include = 1 + memoSolve(i + 1, j2 + 1)
            noTake = memoSolve(i + 1, j)
            
            memo[i][j] = max(include, noTake)
            return memo[i][j]
            
        return memoSolve(0,0)

import math

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        m = len(text1)
        n = len(text2)
        
        if m == 0 or n == 0:
            return 0
        
        prev = [0]*(n+1)
        curr = [0] + [-math.inf]*n
            
        for a in range(1, m+1):
            for b in range(1, n + 1):
                if text1[a-1] == text2[b-1]:
                    curr[b] = 1 + prev[b-1]
                else:
                    curr[b] = max(curr[b-1], prev[b])
            
            prev = curr
            curr = [0] + [-math.inf]*n
        
        return prev[n]


class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        def helper(text1, text2,i,j,memo):
            if i == len(text1) or j == len(text2):
                return 0
            if memo[i][j] < 0:
                c1 = text1[i]
                c2 = text2[j]
                if c1 == c2:
                    memo[i+1][j+1] = helper(text1,text2,i+1,j+1,memo)
                    memo[i][j] = 1 + memo[i+1][j+1]
                else:
                    memo[i+1][j] = helper(text1,text2,i+1,j,memo)
                    memo[i][j+1] = helper(text1,text2,i,j+1,memo)
                    memo[i][j] = max(memo[i+1][j],memo[i][j+1])
            return memo[i][j]
        
        n = len(text1)
        m = len(text2)
        memo = [[-1 for _ in range(0,m+1)] for _ in range(0,n+1)]
        
        
        return helper(text1,text2,0,0,memo)

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
#         dp = [[0] * (len(text1) + 1) for _ in range(len(text2) + 1)]
        
#         # logic: if same, add 1, else max(try each without first)
#         # if row,col V == same, == prev diag + 1
#         # else: = max(row-1,col, row,col-1)
        
#         for row in range(1, len(text2) + 1):
#             for col in range(1, len(text1) + 1):
#                 if text2[row - 1] == text1[col - 1]:
#                     dp[row][col] = dp[row-1][col-1] + 1
#                 else:
#                     dp[row][col] = max(dp[row-1][col], dp[row][col-1])
        
#         return dp[-1][-1]
    
        memo = {}
        def lcs(i, j):
            if i == len(text1) or j == len(text2):
                return 0
            if (i, j) in memo:
                return memo[(i, j)]
            elif text1[i] ==  text2[j]:
                r = 1 + lcs(i + 1, j + 1)
            else:
                r = max(lcs(i + 1, j), lcs(i, j + 1))
                
            memo[(i, j)] = r
            return r
        
        return lcs(0, 0)

from functools import wraps

class Solution:
    def longestCommonSubsequence(self, text1, text2):

        def cache_decorator(f):
            _cache = {}

            @wraps(f)
            def new_f(*args):
                if args not in _cache:
                    _cache[args] = f(*args)
                return _cache[args]

            return new_f

        @cache_decorator
        def compute(x, y):
            if x == len(text1):
                return 0
            if y == len(text2):
                return 0

            if text1[x] == text2[y]:
                return 1 + compute(x+1, y+1)

            return max([compute(x+1, y), compute(x, y+1)])

        return compute(0, 0)



class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        
        
        def lcs_helper(index1, index2, memo = {}):
        
            if index1 == len(text1) or index2 == len(text2):
                return 0
            key = (index1, index2)
            if key not in memo:

                if text1[index1] == text2[index2]:
                    memo[key] = 1 + lcs_helper(index1+1, index2+1, memo)
                else:
                    memo[key] =  max(lcs_helper(index1, index2+1,memo),
                           lcs_helper(index1+1, index2, memo))
            return memo[key]
        
        return lcs_helper(0,0)
        
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
#     def longestCommonSubsequence(self, text1: str, text2: str) -> int:
#         max_count = float(\"-inf\")
        
#         for _ in range(len(text1)):
#             curr_count = 0
#             left_index = 0
#             for index in range(_,len(text1)):
#                 char = text1[index]
#                 if text2.find(char, left_index) != -1:
#                     curr_count +=1
#                     left_index = text2.find(char, left_index) + 1
#                     remaining_string = text2[left_index:]
#             max_count = max(max_count, curr_count)
                
#         return max_count
                
                


import numpy as np
class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        
        l1 = len(text1)
        l2 = len(text2)
        
        dp = np.zeros((l1+1, l2+1), dtype = int)
        
        dp[:][0] = 0
        dp[0][:] = 0
            
        for i in range(1, l1+1):
            for j in range(1, l2+1):
                if text1[i-1] == text2[j-1]:
                    dp[i][j] = 1 + dp[i-1][j-1]
                else:
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])
                    
        return dp[-1][-1]
        
        


class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        cache = { }
        
        def dfs( i, j, count):
            
            if i == len(text1) or j == len(text2):
                return 0
            
            if (i,j) in cache:
                return cache[(i,j)]
            
            if text1[i] == text2[j]:
                #count += 1
                return 1 + dfs( i+1, j+1, count)
                
            a = dfs( i+1, j,   count  )
            b = dfs( i,   j+1, count )
            c = max(a,b)
            
            cache[(i,j)] = c
            return c
        
        return dfs( 0, 0, 0 )


class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        def helper(i, j):
            if i == n1 or j==n2:
                self.h[i,j] = 0
                return 0
            
            if (i,j) in self.h:
                return self.h[i,j]
            
            if text1[i]==text2[j]:
                self.h[i,j] = helper(i+1, j+1)+1
            else:
                self.h[i,j] = max(helper(i+1, j), helper(i, j+1))
            
            return self.h[i,j]
                
        
        n1 = len(text1)
        n2 = len(text2)
        
        self.h = {}
        
        res = helper(0, 0)
        
        return res

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        memo = {}
        def recurse(i1, i2):
            if i1 >= len(text1) or i2 >= len(text2):
                return 0
            
            if (i1, i2) in memo:
                return memo[(i1, i2)]
            
            if text1[i1] == text2[i2]:
                memo[(i1, i2)] = 1 + recurse(i1+1, i2+1)
            else:
                memo[(i1, i2)] = max(recurse(i1+1, i2), recurse(i1, i2+1))
            
            return memo[(i1, i2)]
        
        return recurse(0, 0)


class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        
        
        if(len(text1) < len(text2)):
            text1,text2 = text2,text1
        
        row = len(text2)
        col = len(text1) + 1
      
        # dp = [[0 for _ in range(col)] for _ in range(row)]
        
        dp = [0 for _ in range(col)]
        
        for i in range(row):
            pre = 0
            for j in range(1,col):
                
                temp = dp[j]
                if(text1[j-1] == text2[i]):
                    dp[j] = pre + 1
                    # dp[i][j] = dp[i-1][j-1] + 1
                else:
                    dp[j] = max(dp[j-1],dp[j])
                    # dp[i][j] = max(dp[i-1][j],dp[i][j-1])
                pre = temp
        
        return dp[-1]


class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
#         dp = [[0] * (len(text1) + 1) for _ in range(len(text2) + 1)]
        
#         # logic: if same, add 1, else max(try each without first)
#         # if row,col V == same, == prev diag + 1
#         # else: = max(row-1,col, row,col-1)
        
#         for row in range(1, len(text2) + 1):
#             for col in range(1, len(text1) + 1):
#                 if text2[row - 1] == text1[col - 1]:
#                     dp[row][col] = dp[row-1][col-1] + 1
#                 else:
#                     dp[row][col] = max(dp[row-1][col], dp[row][col-1])
        
#         return dp[-1][-1]
        from functools import lru_cache

        memo = {}
        @lru_cache(maxsize=None)
        def lcs(i, j):
            if i == len(text1) or j == len(text2):
                return 0
            if (i, j) in memo:
                return memo[(i, j)]
            elif text1[i] ==  text2[j]:
                r = 1 + lcs(i + 1, j + 1)
            else:
                r = max(lcs(i + 1, j), lcs(i, j + 1))
                
            memo[(i, j)] = r
            return r
        
        return lcs(0, 0)

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:

        memo = {}
        def helper(i, j):
            if i >= len(text1) or j >= len(text2):
                return 0
            if (i,j) in memo:
                return memo[(i,j)]
            if text1[i] == text2[j]:
                memo[(i,j)] = 1 + helper(i+1, j+1)
                return memo[(i,j)]
            else:
                memo[(i,j)] = max(helper(i, j+1), helper(i+1, j))
                return memo[(i,j)]

        return helper(0, 0)

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        memo = dict()
        def solve(i, j):
            if i == len(text1) or j == len(text2):
                return 0
            
            if (i, j) in memo:
                return memo[(i, j)]
            
            if text1[i] == text2[j]:
                ans = 1 + solve(i+1, j+1)
            else:
                ans = max(solve(i+1, j), solve(i, j+1))
                
            memo[(i, j)] = ans
            return ans
        
        return solve(0, 0)


class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        import numpy as np
        x=list(text1)
        y=list(text2)
        m=len(x)
        n=len(y)
        t=-1* np.ones((m+1,n+1))
        for j in range(m+1):
            t[j][0]=0
        for i in range(n+1):
            t[0][i]=0
        print(t)
        for i in range(1,n+1):
            for j in range(1,m+1):
                if x[j-1]==y[i-1]:
                    t[j][i]=1+t[j-1][i-1]
                else:
                    t[j][i]=max(t[j-1][i],t[j][i-1])
        return int(t[m][n])

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        def helper(i, j):
            if (i,j) in self.h:
                return self.h[i,j]
            
            if i == n1 or j==n2:
                self.h[i,j] = 0
                return 0

            if text1[i]==text2[j]:
                self.h[i,j] = helper(i+1, j+1)+1
            else:
                self.h[i,j] = max(helper(i+1, j), helper(i, j+1))
            
            return self.h[i,j]
                
        
        n1 = len(text1)
        n2 = len(text2)
        
        self.h = {}
        
        res = helper(0, 0)
        
        return res
        
#         n1 = len(text1)
#         n2 = len(text2)
#         s1 = '*'+text1
#         s2 = '*'+text2
        
#         if n1==0 or n2==0:
#             return 0
        
#         res = [[0 for _ in range(n2+1)] for _ in range(n1+1)]
        
#         for i in range(1, n1+1):
#             for j in range(1, n2+1):
#                 if s1[i] == s2[j]:
#                     res[i][j] = res[i-1][j-1]+1
#                 else:
#                     res[i][j] = max(res[i][j-1], res[i-1][j])
        
#         return res[-1][-1]


class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        cache = {}
        def lcs(i, j):
            if i == len(text1) or j == len(text2): return 0
            if (i, j) in cache: return cache[(i, j)]
            if text1[i] == text2[j]: 
                cache[(i, j)] = 1+lcs(i+1, j+1)
                return cache[(i, j)]
            cache[(i, j)] = max(lcs(i+1, j), lcs(i, j+1))
            return cache[(i, j)]
        return lcs(0,0)
            


class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        def helper(i1, i2):
            if (i1, i2) in self.memo:
                return self.memo[(i1, i2)]
            
            res = 0
            if i1 == len(text1) or i2 == len(text2):
                res = 0
            elif text1[i1] == text2[i2]:
                res = 1 + helper(i1 + 1, i2 + 1)
            else:
                res = max(helper(i1 + 1, i2), helper(i1, i2 + 1))
            
            self.memo[(i1, i2)] = res
            return self.memo[(i1, i2)]
        
        self.memo = {}
        return helper(0, 0)

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        def helper(i,j, dc):
            if i<0 or j<0:
                return 0
            if (i,j) in dc:
                return dc[(i,j)]
            
            if text1[i] == text2[j]:
                dc[(i,j)] = helper(i-1,j-1,dc) + 1
                return dc[(i,j)]
            else:
                dc[(i,j)] = max(helper(i-1,j,dc),
                                helper(i,j-1,dc))
                return dc[(i,j)]
        return helper(len(text1)-1,len(text2)-1,{})
            


class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        self.memo = {}
        self.t1 = text1
        self.t2 = text2
        
        tup = (len(text1), len(text2))
        return self.helper(tup)
    
    def helper(self, tup):
        
        if tup in self.memo:
            return self.memo[tup]
        elif tup[0] == 0 or tup[1] == 0:
            return 0
        elif self.t1[tup[0]-1] == self.t2[tup[1]-1]:
            x = (tup[0]-1, tup[1]-1)
            self.memo[tup] = 1+self.helper(x)
        else:
            a = (tup[0]-1, tup[1])
            b = (tup[0], tup[1]-1)
            
            self.memo[tup] = max(
                self.helper(a),
                self.helper(b))
            
        return self.memo[tup]

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        if len(text2) < len(text1):
            text1, text2 = text2, text1
            
        prev = [0] * (len(text1) + 1)
        
        # logic: if same, add 1, else max(try each without first)
        # if row,col V == same, == prev diag + 1
        # else: = max(row-1,col, row,col-1)
        
        for row in range(1, len(text2) + 1):
            curr = [0] * (len(text1) + 1)
            for col in range(1, len(text1) + 1):
                if text2[row - 1] == text1[col - 1]:
                    curr[col] = prev[col-1] + 1
                else:
                    curr[col] = max(prev[col], curr[col-1])
            prev = curr
        
        return prev[-1]
#         from functools import lru_cache

#         memo = {}
#         def lcs(i, j):
#             if (i, j) in memo:
#                 return memo[(i, j)]
#             if i == len(text1) or j == len(text2):
#                 r = 0
#             elif text1[i] ==  text2[j]:
#                 r = 1 + lcs(i + 1, j + 1)
#             else:
#                 r = max(lcs(i + 1, j), lcs(i, j + 1))
                
#             memo[(i, j)] = r
#             return r
        
#         return lcs(0, 0)


class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        cache = {}
        def lcs(i, j):
            if i == len(text1) or j == len(text2): return 0
            if (i, j) in cache: return cache[(i, j)]
            if text1[i] == text2[j]: return 1+lcs(i+1, j+1)
            cache[(i, j)] = max(lcs(i+1, j), lcs(i, j+1))
            return cache[(i, j)]
        return lcs(0,0)
            


class Solution:
    # def longestCommonSubsequence(self, text1: str, text2: str) -> int:
    #     matrix = [[None]*(len(text2)+1) for i in range(len(text1)+1)]
    #     for j in range(len(text2)+1):
    #         matrix[0][j] = 0
    #     for i in range(len(text1)+1):
    #         matrix[i][0] = 0
    #     for i in range(1, len(text1)+1):
    #         for j in range(1, len(text2)+1):
    #             if text1[i-1] == text2[j-1]:
    #                 matrix[i][j] = 1 + matrix[i-1][j-1]
    #             else:
    #                 matrix[i][j] = max(matrix[i-1][j], matrix[i][j-1])
    #     return matrix[len(text1)][len(text2)]
    
    
    
    
    
    

    
    
    


    def longestCommonSubsequence(self, s1, s2):
        def _longest_common_subsequence(s1, s2, cache):
            p = (len(s1), len(s2))
            if p in cache:
                return cache[p]
            elif len(s1) == 0 or len(s2) == 0:
                return 0
            elif s1[-1] == s2[-1]:
                answer = 1 + _longest_common_subsequence(s1[:-1], s2[:-1], cache)
                cache[p] = answer
                return answer
            else:
                answer = max(_longest_common_subsequence(s1, s2[:-1], cache), _longest_common_subsequence(s1[:-1], s2, cache))
                cache[p] = answer
                return answer
        return _longest_common_subsequence(s1, s2, {})

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        if len(text1) == 0 or len(text2) == 0:
            return 0
        
        grid = [[[None, 0, None, None] for i in range(len(text1) + 1)] for i in range(len(text2) + 1)] 
        
        for i in range(1, len(text2) + 1):
            for j in range(1, len(text1) + 1):
                if text1[j - 1] == text2[i - 1]:
                    grid[i][j] = [text2[i - 1], grid[i - 1][j - 1][1] + 1, i - 1, j - 1]
                else:
                    if grid[i - 1][j][1] > grid[i][j - 1][1]:
                        grid[i][j] = [None, grid[i - 1][j][1], i - 1, j]
                    else:
                        grid[i][j] = [None, grid[i][j - 1][1], i, j - 1]
        return grid[-1][-1][1]


class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        
        def helper( memo, p1, p2 ):

            if p1 >= len(text1) or p2 >= len(text2):
                return 0
            
            if (p1, p2) in memo:
                return memo[(p1, p2)]
            
            if text1[p1] == text2[p2]:
                return 1 + helper( memo, p1+1, p2+1 )
          
            c1 = helper( memo, p1+1, p2 )
            c2 = helper( memo, p1, p2+1 )

            memo[(p1, p2)] = max(c1, c2) 
            return memo[(p1, p2)]

        # need to memoize the p1, p2, and length
        memo = {}
        return helper( memo, 0, 0 )

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        
        def helper( memo, p1, p2 ):

            if p1 >= len(text1) or p2 >= len(text2):
                return 0
            
            if (p1, p2) in memo:
                return memo[(p1, p2)]
            
            if text1[p1] == text2[p2]:
                return 1 + helper( memo, p1+1, p2+1 )

            c1 = helper( memo, p1+1, p2 )
            c2 = helper( memo, p1, p2+1 )

            memo[(p1, p2)] = max( c1, c2 )
            return memo[(p1, p2)]

        # need to memoize the p1, p2, and length
        memo = {}
        return helper( memo, 0, 0 )

class Solution:
    # def longestCommonSubsequence(self, text1: str, text2: str) -> int:
    #     matrix = [[None]*(len(text2)+1) for i in range(len(text1)+1)]
    #     for j in range(len(text2)+1):
    #         matrix[0][j] = 0
    #     for i in range(len(text1)+1):
    #         matrix[i][0] = 0
    #     for i in range(1, len(text1)+1):
    #         for j in range(1, len(text2)+1):
    #             if text1[i-1] == text2[j-1]:
    #                 matrix[i][j] = 1 + matrix[i-1][j-1]
    #             else:
    #                 matrix[i][j] = max(matrix[i-1][j], matrix[i][j-1])
    #     return matrix[len(text1)][len(text2)]
    
    
    
    
    
    

    
    
    
    def _longest_common_subsequence(self, s1, s2, cache):
        p = (len(s1), len(s2))
        if p in cache:
            return cache[p]
        elif len(s1) == 0 or len(s2) == 0:
            return 0
        elif s1[-1] == s2[-1]:
            answer = 1 + self._longest_common_subsequence(s1[:-1], s2[:-1], cache)
            cache[p] = answer
            return answer
        else:
            answer = max(self._longest_common_subsequence(s1, s2[:-1], cache), self._longest_common_subsequence(s1[:-1], s2, cache))
            cache[p] = answer
            return answer

    def longestCommonSubsequence(self, s1, s2):
        return self._longest_common_subsequence(s1, s2, {})

class Solution:
    def longestCommonSubsequence1(self, s1: str, s2: str) -> int:
        m = len(s1)
        n = len(s2)
        memo = [[-1 for _ in range(n + 1)] for _ in range(m + 1)]
        return self.helper(s1, s2, 0, 0, memo)

    def helper(self, s1, s2, i, j, memo):
        if memo[i][j] < 0:
            if i == len(s1) or j == len(s2):
                memo[i][j] = 0
            elif s1[i] == s2[j]:
                memo[i][j] = 1 + self.helper(s1, s2, i + 1, j + 1, memo)
            else:
                memo[i][j] = max(
                    self.helper(s1, s2, i + 1, j, memo),
                    self.helper(s1, s2, i, j + 1, memo),
                )
        return memo[i][j]
        
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        def helper(i1, i2):
            if (i1, i2) in self.memo:
                return self.memo[(i1, i2)]
            
            res = 0
            if i1 == len(text1) or i2 == len(text2):
                res = 0
            elif text1[i1] == text2[i2]:
                res = 1 + helper(i1 + 1, i2 + 1)
            else:
                res = max(helper(i1 + 1, i2), helper(i1, i2 + 1))
            
            self.memo[(i1, i2)] = res
            return self.memo[(i1, i2)]
        
        self.memo = {}
        return helper(0, 0)

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        
        @lru_cache(maxsize=None)
        def helper(i1, i2):
            if i1 == len(text1) or i2 == len(text2):
                return 0
            else:
                if text1[i1] == text2[i2]:
                    return helper(i1+1,i2+1) + 1
                return max(helper(i1+1,i2), helper(i1,i2+1))
        
        return helper(0, 0)

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        m = len(text1)
        n = len(text2)
        dp = [[0] * (n+1) for _ in range(m+1)]
        
        for i in reversed(range(m)):
            for j in reversed(range(n)):
                if text1[i] == text2[j]:
                    dp[i][j] = dp[i+1][j+1] + 1
                else:
                    dp[i][j] = max(dp[i+1][j], dp[i][j+1])
                    
        return dp[0][0]

from collections import defaultdict
class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        dp = defaultdict(lambda: -1)
        
        def helper(n, m):
            if m < 0 or n < 0:
                return 0
            
            if dp[(m, n)] == -1:
                if text1[n] == text2[m]:
                    length = 1 + helper(n-1, m-1)
                else:
                    length = max(helper(n-1, m), 
                                helper(n, m-1))
                dp[(m, n)] = length
            return dp[(m, n)]
        return helper(len(text1)-1, len(text2)-1)

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        @lru_cache(None)
        def lcs(s1,n,i,s2,m,j):
            if i>=n or j>=m:
                return 0
            if s1[i]==s2[j]:
                return 1 + lcs(s1,n,i+1,s2,m,j+1)
            return max(lcs(s1,n,i+1,s2,m,j),lcs(s1,n,i,s2,m,j+1))
        return lcs(text1,len(text1),0,text2,len(text2),0)


class Solution:
    import functools
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        longest = 0
        memo = {}
        # represents the lcs of the substring text1[:i] and text2[:j]
        def calc_lcs(i, j):
            if i < 0 or j < 0: return 0
            if (i, j) in memo: return memo[(i, j)]
            # if the char at the end of the substring text1[:i] == text2[:j], then
            # we don't have to \"split out\" to search for the next common character, because we are already
            # there!. so simply return 1 + calclcs(i - 1, j - 1)
            if text1[i] == text2[j]: return 1 + calc_lcs(i - 1, j - 1)
            # however, if the char at the end of the subtring text1[:i] DOESNT equal the char at the end 
            # of the substring text2[:j], then we have to \"split out\", to try to find the next common 
            # character. For example, say we had the strings \"abcd\", and \"ac\". Clearly, 'c' doesn't equal 
            # 'd'. So what do we do? We have to try to find either the next occurence of 'd' in the 
            # second string, or the next occurence of 'c' in the first string. What if both occur?
            # well thats why we are taking the max! If both occur, it will result several \"lcs\"s being
            # calculuated, and we want the largest one!
            memo[(i, j)] = max(calc_lcs(i, j - 1), calc_lcs(i - 1, j))
            return memo[(i, j)]
        return calc_lcs(len(text1) - 1, len(text2) - 1)
            


from functools import lru_cache

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        if not text1 or not text2:
            return 0
        n, m = len(text1), len(text2)
        
        @lru_cache(maxsize=10000)
        def lcs(i, j):
            if i > n-1 or j > m-1:
                return 0
            if text1[i] == text2[j]:
                return lcs(i+1, j+1) + 1
            return max(lcs(i+1, j), lcs(i, j+1))
            
        return lcs(0, 0)
                


class Solution:
    # 定义dp(i, j)是tex1中以i开头的和text2中以j开头的最长common subsequence
    # time O(mn) space O(mn)
    # 一般这种两个string/array让你dp的，都是定义以i/j为起点/终点的个数/长度
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        if not text1 or not text2: return 0
        
        n, m = len(text1), len(text2)
        M = {}
        ret = 0
        # 和longest palindromic subsequence的dp状态转移一样
        def dp(i, j):
            if i >= n or j >= m:
                return 0
            
            if (i, j) in M: 
                return M[(i, j)]
            
            M[(i, j)] = 0
            if text1[i] == text2[j]:
                M[(i, j)] = 1+dp(i+1, j+1)
            else:
                M[(i, j)] = max(dp(i+1, j), dp(i, j+1))
                
            return M[(i, j)]
        
        return dp(0, 0)

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
    #     # return self.recursive(text1, text2, 0, 0)
        dp = dict()
        return self.top_down(dp, text1, text2, 0, 0)
        # return self.bottom_up(text1, text2)
    
    def recursive(self, text1, text2, i, j):
        if i >= len(text1) or j >= len(text2):
            return 0
        if text1[i] == text2[j]:
            return 1+self.recursive(text1, text2, i+1, j+1)
        a = self.recursive(text1, text2, i+1, j)
        b = self.recursive(text1, text2, i, j+1)
        return max(a, b)
    
    def top_down(self, dp, text1, text2, i, j):
        if i >= len(text1) or j >= len(text2):
            return 0
        if text1[i] == text2[j]:
            return 1+self.top_down(dp, text1, text2, i+1, j+1)
        if (i, j) in dp:
            return dp[(i, j)]
        a = self.top_down(dp, text1, text2, i+1, j)
        b = self.top_down(dp, text1, text2, i, j+1)
        dp[(i, j)] = max(a, b)
        return dp[(i, j)]

    def bottom_up(self, text1, text2):
        i, j = 0, 0
        m, n = len(text1), len(text2)
        dp = [[0]*(n+1) for _ in range(m+1)]
        for i in range(1, m+1):
            for j in range(1, n+1):
                if text1[i-1] == text2[j-1]:
                    dp[i][j] = 1+dp[i-1][j-1]
                else:
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])
        return dp[-1][-1]


class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        mp = {}
        def lcs(i, j):
            if i>=len(text1) or j >=len(text2):
                return 0
            elif (i,j) in mp:
                return mp[(i,j)]
            else:
                if text1[i] == text2[j]:
                    mp[(i,j)] = 1+ lcs(i+1,j+1)
                else:
                    mp[(i,j)] = max(lcs(i+1,j), lcs(i,j+1))
                return mp[(i,j)]
        lcs(0,0)
        return max(mp.values())

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        #hashh={}
        def helper(text1,text2,i,j,hashh):
            if i>=len(text1) or j>=len(text2):
                return 0
            leftElement=text1[i]
            rightElement=text2[j]
            if (i,j) in hashh:
                return hashh[(i,j)]
            if text1[i]==text2[j]:
                hashh[(i,j)]=1+helper(text1,text2,i+1,j+1,hashh)
            else:
                temp1=helper(text1,text2,i+1,j,hashh)
                temp2=helper(text1,text2,i,j+1,hashh)
                hashh[(i,j)]=max(temp1,temp2)
            return hashh[(i,j)]
        return helper(text1,text2,0,0,{})

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        prev=[0 for j in range(len(text2)+1)]
        curr=[0 for j in range(len(text2)+1)]
        for i in range(len(text1)):
            curr=[0 for j in range(len(text2)+1)]
            for j in range(len(text2)):
                
                if text1[i]==text2[j]:
                    curr[j+1]=prev[j]+1
                    
                else:
                    curr[j+1]=max(prev[j+1],curr[j])
                    
            prev=curr
                    
        return prev[len(text2)]

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        if len(text1) == 0 or len(text2) == 0:
            return 0

        mem = [[-1 for _ in range(len(text2) + 1)] for _ in range(len(text1) + 1)]
        return self.compute(mem, 0, 0, text1, text2)

    def compute(self, mem, ptr1, ptr2, text1, text2):
        # we are at the end
        if ptr1 == len(text1) or ptr2 == len(text2):
            return 0

        if mem[ptr1][ptr2] != -1:
            return mem[ptr1][ptr2]

        if text1[ptr1] == text2[ptr2]:
            ans = 1 + self.compute(mem, ptr1 + 1, ptr2 + 1, text1, text2)
            mem[ptr1][ptr2] = ans
            return ans
        else:
            ans = max(self.compute(mem, ptr1 + 1, ptr2, text1, text2), self.compute(mem, ptr1, ptr2 + 1, text1, text2))
            mem[ptr1][ptr2] = ans
            return ans


class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        dp = [[0 for j in range(len(text2))] for i in range(len(text1))]
        
        dp[0][0] = int(text1[0] == text2[0])
        # print(dp[0][0], text1[0], text2[0], text1[0] == text2[0], int(text1[0] == text2[0]), int(True))
        
        for i in range(1, len(text1)):
            dp[i][0] = max(int(text1[i] == text2[0]), dp[i-1][0])
            
        for j in range(1, len(text2)):
            dp[0][j] = max(int(text2[j] == text1[0]), dp[0][j-1])
        
        for i in range(1, len(text1)):
            for j in range(1, len(text2)):
                
                if text1[i] == text2[j]:
                    dp[i][j] = dp[i-1][j-1] + 1
                else:
                    dp[i][j] = max(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])
        
        print(dp)
        return dp[-1][-1]

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        memo = {}
        def helper(s1,s2,i1,i2):
            if not s1 or not s2:
                return 0
            if (i1,i2) in memo:
                return memo[(i1,i2)]
            if s1[0] == s2[0]:
                memo[(i1,i2)] = 1+helper(s1[1:],s2[1:],i1+1,i2+1)
            else:
                memo[(i1,i2)] =  max(helper(s1[1:],s2,i1+1,i2),helper(s1,s2[1:],i1,i2+1))
            return memo[(i1,i2)]
            
        
        
        
        
        
        
        return helper(text1,text2,0,0)

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        
        cache = [[-1 for _ in range(len(text2))] for _ in range(len(text1))]
        
        def lcs(text1, text2, i, j, cache):
            
            if i >= len(text1) or j >= len(text2):
                return 0
            if cache[i][j] != -1:
                return cache[i][j]
            elif text1[i] == text2[j]:
                return 1 + lcs(text1, text2, i+1, j+1, cache)
            else:
                cache[i][j] = max(lcs(text1, text2, i, j+1, cache), lcs(text1, text2, i+1, j, cache))
                return cache[i][j]
            
        
        
        a = lcs(text1, text2, 0, 0, cache)
        # print(cache)
        
        return a

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        cache = {}
        
        def solve(t1,t2):
            if t1 == len(text1) or t2 == len(text2):
                return 0
            
            #check cache
            if (t1,t2) in cache:
                return cache[(t1,t2)]
            
            #case1
            if text1[t1] == text2[t2]:
                opt1 = solve(t1+1,t2+1)
                cache[(t1+1,t2+1)] = opt1
                return 1 + opt1
            
            #case2
            else:
                opt1 = solve(t1,t2+1)
                opt2 = solve(t1+1,t2)
                cache[(t1,t2+1)] = opt1
                cache[(t1+1,t2)] = opt2
                return max(opt1,opt2)
                
        return solve(0,0)

from functools import lru_cache
class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        t1,t2= text1,text2
        @lru_cache(None)
        def lcsh(m,n):
            nonlocal t1,t2
            if m==0 or n==0:
                return 0
            if t1[m-1]==t2[n-1]:
                return 1 + lcsh(m-1,n-1)
            else:
                return max(lcsh(m-1,n),lcsh(m,n-1))
        return lcsh(len(text1),len(text2))

class Solution:
    
    def lcs(self, i, j):
        if (i, j) not in self.memo:
            if i == len(self.s) or j == len(self.p):
                ans =  0
            elif self.s[i] == self.p[j]:
                ans = self.lcs(i+1, j+1) + 1
            else:
                ans = max(self.lcs(i+1, j), self.lcs(i, j+1))
            self.memo[(i, j)] = ans
        return self.memo[(i, j)]
    
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        self.s, self.p = text1, text2
        self.memo = {}
        return self.lcs(0, 0)

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        def helper(i1, i2):
            if i1 == len(text1) or i2 == len(text2):
                return 0
            
            if (i1, i2) in self.memo:
                return self.memo[(i1, i2)]
            
            res = 0
            if text1[i1] == text2[i2]:
                res = 1 + helper(i1 + 1, i2 + 1)
            else:
                res = max(helper(i1 + 1, i2), helper(i1, i2 + 1))
            
            self.memo[(i1, i2)] = res
            return self.memo[(i1, i2)]
        
        self.memo = {}
        return helper(0, 0)

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        matrix = [0]*(len(text2)+1)
        for i in range(1, len(text1)+1):
            p = 0
            for j in range(1, len(text2)+1):
                if text1[i-1] == text2[j-1]:
                    t = matrix[j]
                    matrix[j] = 1 + p
                    p = t
                else:
                    p = matrix[j]
                    matrix[j] = max(matrix[j], matrix[j-1])
        return matrix[len(text2)]

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        dp = [-1] * len(text1)
        for i in range(len(dp)):
            dp[i] = [-1] * len(text2)
        
        self.dp = dp
        self.t1 = text1
        self.t2 = text2
        
        return self.LCSHelper(len(text1)-1, len(text2)-1)
    
    def LCSHelper(self, i, j):
        if i < 0 or i >= len(self.t1) or j < 0 or j >= len(self.t2):
            return 0
        
        if self.dp[i][j] != -1:
            return self.dp[i][j]
        
        if self.t1[i:i+1] == self.t2[j:j+1]:
            self.dp[i][j] = 1 + self.LCSHelper(i-1, j-1)
        else:
            self.dp[i][j] = max(self.LCSHelper(i, j-1), self.LCSHelper(i-1, j))
        
        return self.dp[i][j]

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        hashh={}
        def helper(text1,text2,i,j):
            if i>=len(text1) or j>=len(text2):
                return 0
            leftElement=text1[i]
            rightElement=text2[j]
            if (i,j) in hashh:
                return hashh[(i,j)]
            if text1[i]==text2[j]:
                hashh[(i,j)]=1+helper(text1,text2,i+1,j+1)
                #return hashh[(i+1,j+1)]
            else:
                temp1=helper(text1,text2,i+1,j)
                temp2=helper(text1,text2,i,j+1)
                hashh[(i,j)]=max(temp1,temp2)
            return hashh[(i,j)]
        return helper(text1,text2,0,0)

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        def lcs(i, j):
            
            if i > len(text1)-1 or j > len(text2)-1:
                return 0
            if (i,j) in memo:
                return memo[(i,j)]
            if text1[i] == text2[j]:
                memo[(i,j)] = 1 + lcs(i+1, j+1)
            else:
                memo[(i,j)] = max(lcs(i+1, j), lcs(i, j+1))
                
            return memo[(i,j)]
            
            
        memo = {}
        return lcs(0,0)

from functools import lru_cache
class Solution:
    def longestCommonSubsequence(self, text1, text2):
        
        @lru_cache(maxsize=None)
        def memo_solve(p1, p2):
            
            # Base case: If either string is now empty, we can't match
            # up anymore characters.
            if p1 == len(text1) or p2 == len(text2):
                return 0
            
            # Recursive case 1.
            if text1[p1] == text2[p2]:
                return 1 + memo_solve(p1 + 1, p2 + 1)
            
            # Recursive case 2.
            else:
                return max(memo_solve(p1, p2 + 1), memo_solve(p1 + 1, p2))
            
        return memo_solve(0, 0)

# class Solution:
#     def longestCommonSubsequence(self, s1: str, s2: str) -> int:
        
#         len_s1, len_s2 = len(s1), len(s2)
        
#         @lru_cache(None)
#         def dp(i, j):
#             if i == len_s1 or j == len_s2:
#                 return 0
            
#             if s1[i] == s2[j]:
#                 return 1 + dp(i+1, j+1)
            
#             return max(dp(i+1, j), dp(i, j+1))
        
#         return dp(0, 0)

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        memo = {}
        
        def lcs(i, j):
            if (i, j) in memo:
                return memo[(i, j)]
            
            if i == len(text1) or j == len(text2):
                return 0
            
            move_both = None
            if text1[i] == text2[j]:
                move_both = 1 + lcs(i+1, j+1)
                
            move_i = lcs(i+1, j)
            move_j = lcs(i, j+1)
            memo[(i, j)] = max(move_i, move_j) if move_both is None else max([move_i, move_j, move_both])
            return memo[(i, j)]
        
        return lcs(0, 0)

def dp(s1, s2, i, j, mem):
    if i >= len(s1) or j >= len(s2):
        return 0
    elif (i, j) in mem:
        return mem[(i, j)]
    
    l = dp(s1, s2, i+1, j, mem)
    r = dp(s1, s2, i, j+1, mem)
    both = (1 + dp(s1, s2, i+1, j+1, mem)) if s1[i] == s2[j] else 0
    res = max(r, l, both)
    mem[(i, j)] = res
    return res

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        return dp(text1, text2, 0, 0, {})

class Solution:
    def longestCommonSubsequence(self, s1: str, s2: str) -> int:
        @lru_cache(maxsize = 10**18)
        def LCS(s1 , s2 , n1 , n2):
            if n1 == 0 or n2 == 0:return 0 
            if s1[n1-1] == s2[n2 - 1]:return 1 + LCS(s1,s2,n1-1,n2-1)
            else:return max(LCS(s1,s2,n1-1,n2),LCS(s1,s2,n1,n2-1))
        return(LCS(s1,s2,len(s1),len(s2)))

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        t=[[-1 for j in range(len(text2)+1)]for i in range(len(text1)+1)]
        for i in range(len(text1)+1):
            for j in range(len(text2)+1):
                t[0][j] = 0
                t[i][0] = 0
        res = self.LCS(text1,text2,len(text1), len(text2),t)
        return res
    def LCS(self,s1,s2,n,m,t):
        if(t[n][m]!=-1):
            return t[n][m]
        
        elif(s1[n-1]==s2[m-1]):
            t[n][m] =  self.LCS(s1,s2,n-1,m-1,t) +1
            return t[n][m]
        
        elif(s1[n-1]!=s2[m-1]):
            t[n][m] = max(self.LCS(s1,s2,n-1,m,t), self.LCS(s1,s2,n,m-1,t))
            return t[n][m]
        


class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        if len(text1) > len(text2):
            text1, text2 = text2, text1
        matrix = [0]*(len(text2)+1)
        for i in range(1, len(text1)+1):
            p = 0
            for j in range(1, len(text2)+1):
                if text1[i-1] == text2[j-1]:
                    p, matrix[j] = matrix[j], 1 + p
                else:
                    p, matrix[j] = matrix[j], max(matrix[j], matrix[j-1])
        return matrix[len(text2)]

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        memo = {}
        self.dp(text1, text2, len(text1)-1, len(text2)-1, memo)
        
        return memo[(len(text1)-1, len(text2)-1)]
    def dp(self, text1, text2, i, j, memo):
        if i == -1 or j == -1:
            return 0
        if (i,j) in memo:
            return memo[(i,j)]
        
        if text1[i] == text2[j]:
            memo[(i,j)] = self.dp(text1, text2, i-1, j-1, memo) + 1
            return memo[(i,j)]
        else:
            memo[(i,j)] =  max(self.dp(text1, text2, i-1, j, memo), self.dp(text1, text2, i, j-1, memo))
            return memo[(i,j)]
        return memo[(i,j)]
        
        


class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        set1, set2 = set(text1), set(text2)
        if not set1.intersection(set2):
            return 0
        
        dp = [[0 for _ in range(len(text2)+1)] for _ in range(len(text1)+1)]
        for i in range(1, len(text1)+1):
            for j in range(1, len(text2)+1):
                tmp = 0
                if text1[i-1] == text2[j-1]:
                    tmp = 1
                dp[i][j] = max([dp[i-1][j], dp[i][j-1], dp[i-1][j-1]+tmp])
                
        return dp[-1][-1]

class Solution:
    def longestCommonSubsequence(self, t1: str, t2: str) -> int:
        m, n = len(t1), len(t2)
        dp = [[0]*(n+1) for _ in range(m+1)]
        for i in range(1, m+1):
            for j in range(1, n+1):
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
                dp[i][j] = max(dp[i][j], dp[i-1][j-1]+(1 if t1[i-1]==t2[j-1] else 0))
        return dp[-1][-1]


class Solution:
    def __init__(self):
        self.d = {}
        
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        def lcs(p1, p2):
            if p1==len(text1) or p2==len(text2):
                return 0
            if (p1,p2) not in self.d:
                if text1[p1]==text2[p2]:
                    res = 1+lcs(p1+1,p2+1)
                else:
                    res = max( lcs(p1+1,p2), lcs(p1,p2+1) )
                self.d[(p1, p2)] = res
            return self.d[(p1, p2)]
        return lcs(0,0)

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        
        cache = [[None for j in range(len(text2))] for i in range(len(text1))]
        self.memo(text1,text2,0,0,cache)
        return cache[0][0]
    def memo(self,word1,word2,i,j,cache):
        if(i >= len(word1) or j >= len(word2)):
            return 0
        if(word1[i] == word2[j]):
            if(cache[i][j] is None):
                cache[i][j] = 1 + self.memo(word1,word2,i+1,j+1,cache)
            return cache[i][j]
        else:
            if(cache[i][j] is None):
                cache[i][j] = max(self.memo(word1,word2,i+1,j,cache), self.memo(word1,word2,i,j+1,cache))
            return cache[i][j]
        #TLE
        '''
        return self.recurse(text1,text2)
    def recurse(self, word1, word2):
        if(len(word1) == 0 or len(word2) == 0):
            return 0
        if(word1[0] == word2[0]):
            return 1 + self.recurse(word1[1:], word2[1:])
        else:
            return max(self.recurse(word1[1:],word2),self.recurse(word1,word2[1:]))'''

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        dp = {}
        def inner(i,j):
            if i >= len(text1) or j >= len(text2):
                return 0
            
            if dp.get((i,j)) == None:
                if text1[i] == text2[j]:
                    dp[(i,j)] = inner(i+1, j+1) + 1
                else:
                    dp[(i,j)] = max(inner(i+1, j),inner(i, j+1))
            return dp[(i,j)]
        return inner(0,0)        

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        @lru_cache(maxsize=None)
        def memo_solve(p1, p2):
            
            # Base case: If either string is now empty, we can't match
            # up anymore characters.
            if p1 == len(text1) or p2 == len(text2):
                return 0
            
            # Recursive case 1.
            if text1[p1] == text2[p2]:
                return 1 + memo_solve(p1 + 1, p2 + 1)
            
            # Recursive case 2.
            else:
                return max(memo_solve(p1, p2 + 1), memo_solve(p1 + 1, p2))
            
        return memo_solve(0, 0)

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        m, n = len(text1), len(text2)
        dp = [[0] * (n+1) for _ in range(m+1)]
        max_len = 0
        for i in range(1, m+1):
            for j in range(1, n+1):
                dp[i][j] = max(dp[i][j], dp[i-1][j], dp[i][j-1])
                if text1[i-1] == text2[j-1]:
                    dp[i][j] = max(dp[i][j], dp[i-1][j-1] + 1)
                max_len = max(max_len, dp[i][j])
        return max_len


from functools import lru_cache
class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        @lru_cache(maxsize=None)

        
        def helper(p1, p2)->int:
            if p1==len(text1) or p2==len(text2):
                return 0

            option1 = dp[p1+1][p2] if visited[p1+1][p2]==1 else helper(p1+1, p2)
            
            first_occurrence = text2.find(text1[p1], p2)
            if first_occurrence != -1:
                option2 = dp[p1+1][first_occurrence+1] + 1 if visited[p1+1][first_occurrence+1]==1 else 1 + helper(p1+1, first_occurrence+1)
            else:
                option2 = 0
            
            visited[p1][p2] = 1
            dp[p1][p2] = max(option1,option2)
            
            return dp[p1][p2]
        
        dp = [[0]*(len(text2)+1) for _ in range(len(text1)+1)]
        visited = [[0]*(len(text2)+1) for _ in range(len(text1)+1)]
                
        return helper(0, 0)


                    
                
                    
        
        


class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        # return self.recursive(text1, text2, 0, 0)
        dp = dict()
        return self.top_down(dp, text1, text2, 0, 0)
    
    def recursive(self, text1, text2, i, j):
        if i >= len(text1) or j >= len(text2):
            return 0
        if text1[i] == text2[j]:
            return 1+self.recursive(text1, text2, i+1, j+1)
        a = self.recursive(text1, text2, i+1, j)
        b = self.recursive(text1, text2, i, j+1)
        return max(a, b)
    
    def top_down(self, dp, text1, text2, i, j):
        if i >= len(text1) or j >= len(text2):
            return 0
        if text1[i] == text2[j]:
            return 1+self.top_down(dp, text1, text2, i+1, j+1)
        if (i, j) in dp:
            return dp[(i, j)]
        a = self.top_down(dp, text1, text2, i+1, j)
        b = self.top_down(dp, text1, text2, i, j+1)
        dp[(i, j)] = max(a, b)
        return max(a, b)

from collections import defaultdict
class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        dp = defaultdict(lambda: -1)
        def helper(text1, n, text2, m):
            if m == 0 or n == 0:
                return 0
            if dp[(m,n)] == -1:
                if text1[-1] == text2[-1]:
                    length = 1 + helper(text1[:-1], n-1, text2[:-1], m-1)
                else:
                    length = max(helper(text1[:-1], n-1, text2, m), 
                                helper(text1, n,text2[:-1], m-1))
                dp[(m, n)] = length
            return dp[(m, n)]
        return helper(text1, len(text1), text2, len(text2))

class Solution:
    def longestCommonSubsequence(self, s1: str, s2: str) -> int:
        return self.helper(s1, s2, 0, 0)
    @lru_cache(None)
    def helper(self, s1, s2, i, j):
        if i == len(s1) or j == len(s2):
            return 0
        if s1[i] == s2[j]:
            return 1 + self.helper(s1, s2, i + 1, j + 1)
        else:
            return max(self.helper(s1, s2, i+1, j), self.helper(s1, s2, i, j + 1))

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        
        table={}
        def helper(t1, t2, i,j, table):
            if table.get((i,j)) != None:
                return table[(i,j)]
            
            n = len(t1)
            m = len(t2)
            
            if m <=j or n <= i:
                return 0;
            
            
            v = t1[i]
            idx = t2.find(v, j)
            if idx != -1:
                r = max(helper(t1, t2, i+1, j, table), helper(t1, t2, i+1, idx+1, table)+1)
                table[(i,j)] = r 
            else:
                r = helper(t1, t2, i+1,j, table)
                table[(i,j)] = r
            return table[(i,j)]
        
        return helper(text1, text2, 0, 0, table)

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        map = {}
        
        def memo(p1, p2, map):
            #print(concatChar)
            if (p1, p2) in map:
                return map[(p1, p2)]
            else:
                if p1 == len(text1) or p2 == len(text2):
                    return 0
                if text1[p1] == text2[p2]:
                    map[(p1, p2)] = 1 + memo(p1+1, p2+1, map)
                else:
                    map[(p1, p2)] = max(memo(p1, p2+1, map), memo(p1+1, p2, map))
                
                # map[concatChar] = result
                # print(map)
                return map[(p1, p2)]
        
        return memo(0, 0, map)


class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        lookup = [[None for x in range(len(text2))] for y in range(len(text1))]
        def helper(s1, s2, pos1, pos2):
            nonlocal lookup
            if pos1 >= len(s1):
                return 0
            elif pos2 >= len(s2):
                return 0
            elif lookup[pos1][pos2] is not None:
                return lookup[pos1][pos2]
            else:
                if s1[pos1] == s2[pos2]:
                    lookup[pos1][pos2] = max(1 + helper(s1, s2, pos1 + 1, pos2 + 1),
                              helper(s1, s2, pos1 + 1, pos2 + 1),
                              helper(s1, s2, pos1, pos2 + 1),
                              helper(s1, s2, pos1 + 1, pos2))
                    return lookup[pos1][pos2]
                else:
                    lookup[pos1][pos2] = max(helper(s1, s2, pos1 + 1, pos2 + 1),
                              helper(s1, s2, pos1, pos2 + 1),
                              helper(s1, s2, pos1 + 1, pos2))
                    return lookup[pos1][pos2]
        return helper(text1, text2, 0, 0)


class Solution:
    def lcs_helper(self,s1,s2,lookup):
        m, n = len(s1), len(s2)
        lcs_look = lookup.get((m,n),-1)
        if m==0 or n == 0:
            return 0
        if lcs_look != -1:
            return lcs_look
        if s1[-1] == s2[-1]:
            lcs_look = self.lcs_helper(s1[:-1],s2[:-1],lookup)
            lcs_look += 1
            lookup[(m,n)] = lcs_look
            return lcs_look
        else:
            lcs_look1 = self.lcs_helper(s1[:-1],s2,lookup)
            lcs_look2 = self.lcs_helper(s1,s2[:-1],lookup)
            lookup[(m,n)] = max(lcs_look1,lcs_look2)
            return lookup[(m,n)]

    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        m, n = len(text1), len(text2)
        cache = {}
        if m==0 or n == 0:
            return 0
        
        return self.lcs_helper(text1,text2,cache)

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        dp = {}
        l1 = len(text1)
        l2 = len(text2)
        if l1 == 0 or l2 == 0:
            return 0
        for i, c1 in enumerate(text1):
            common = False
            for j, c2 in enumerate(text2):
                seq = 0
                if c1 == c2:
                    if (i-1, j-1) in dp:
                        seq = max(seq, dp[(i-1, j-1)])
                    seq += 1
                else:
                    if (i, j-1) in dp:
                        seq = max(seq, dp[(i, j-1)])
                    if (i-1, j) in dp:
                        seq = max(seq, dp[(i-1, j)])
                dp[(i, j)] = seq
        return dp[(l1-1, l2-1)]

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        
        # Make a grid of 0's with len(text2) + 1 columns
        # and len(text1) + 1 rows
        dp_grid = [[0] * (len(text2) + 1) for _ in range(len(text1) + 1)]
        
        # Iterate up each column, starting from the last one
        for col in reversed(list(range(len(text2)))):
            for row in reversed(list(range(len(text1)))):
                if text2[col] == text1[row]:
                    dp_grid[row][col] = 1 + dp_grid[row + 1][col + 1]
                else:
                    dp_grid[row][col] = max(dp_grid[row + 1][col], dp_grid[row][col + 1])
        return dp_grid[0][0]


class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        def memo(f):
            dic = {}

            def f_alt(*args):
                if args not in dic:
                    dic[args] = f(*args)
                return dic[args]
            return f_alt

        @memo
        def long(i, j):
            if i == -1 or j == -1:
                return 0
            return max(long(i-1,j),long(i,j-1),long(i-1,j-1)+(text1[i] == text2[j]))

        return long(len(text1)-1, len(text2)-1)

import numpy as np
class Solution:
    def longestCommonSubsequence(self, answer_text: str, source_text: str) -> int:
        longest = 0
        answer_text = ' ' + answer_text
        source_text = ' ' + source_text
        words_matrix = np.zeros((len(source_text), len(answer_text)))
        for row in range(1, len(source_text)):
            for col in range(1, len(answer_text)):
                if source_text[row] == answer_text[col]:
                    words_matrix[row][col] = words_matrix[row - 1][col - 1] + 1
                else:
                    words_matrix[row][col] = max(words_matrix[row - 1][col], words_matrix[row][col - 1])
                longest = max(longest, words_matrix[row][col])
        return int(longest)

from functools import lru_cache 

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        @lru_cache(None)
        def helper(t1, t2):
            if not t1 or not t2:
                return 0
            
            if t1[-1] == t2[-1]: 
                return helper(t1[:-1], t2[:-1])  + 1
                
            else:
                return max(helper(t1[:-1], t2), helper(t1, t2[:-1]))
        
        return helper(text1, text2)


class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        cache = [[0]*len(text2) for _ in range(len(text1))]
        return self.helper(text1, 0, text2, 0, cache)
    
    def helper(self, text1:str, i:int, text2:str, j:int, cache):
        
        if i==len(text1) or j==len(text2): return 0
    
        if cache[i][j]!= 0: return cache[i][j]
        
        if text1[i]==text2[j]:
            cache[i][j] = 1+ self.helper(text1, i+1, text2, j+1, cache)
        else:
            cache[i][j] = max(self.helper(text1, i+1, text2, j, cache), self.helper(text1, i, text2, j+1, cache))
            
        return cache[i][j]

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        self.dp = {}
        return self.recursiveLCS(text1, text2, len(text1)-1, len(text2)-1)
        
    def recursiveLCS(self, text1, text2, p1, p2):
        if p1<0 or p2<0:
            return 0
        
        if (p1, p2) in self.dp:
            self.dp[(p1, p2)] = self.dp[(p1, p2)]
            return self.dp[(p1, p2)]
        
        if text1[p1] == text2[p2]:
            self.dp[(p1, p2)] = 1+self.recursiveLCS(text1, text2, p1-1, p2-1)
        else:
            self.dp[(p1, p2)] = max(
                self.recursiveLCS(text1, text2, p1-1, p2),
                self.recursiveLCS(text1, text2, p1, p2-1)
            )
        return self.dp[(p1, p2)]

from typing import *

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        return longestCommonSubsequence_DP(text1, text2, 0, 0, dict())

def longestCommonSubsequence_DP(text1: str, text2: str, first_start_idx: int, second_start_idx: int, memo: Dict):
    if (first_start_idx, second_start_idx) in memo:
        return memo[(first_start_idx, second_start_idx)]

    # base cases
    if first_start_idx == len(text1) or second_start_idx == len(text2):
        return 0

    # recursive cases
    first_cur_char = text1[first_start_idx]
    second_cur_char = text2[second_start_idx]
    ans_if_cur_same = -1
    if first_cur_char == second_cur_char:
        ans_if_cur_same = 1 + longestCommonSubsequence_DP(text1, text2, first_start_idx+1, second_start_idx+1, memo)

    ans1_if_cur_diff = longestCommonSubsequence_DP(text1, text2, first_start_idx, second_start_idx+1, memo)
    ans2_if_cur_diff = longestCommonSubsequence_DP(text1, text2, first_start_idx+1, second_start_idx, memo)

    memo[(first_start_idx, second_start_idx)] = max(ans_if_cur_same if ans_if_cur_same != -1 else -math.inf,
                                                    ans1_if_cur_diff,
                                                    ans2_if_cur_diff)
    return memo[(first_start_idx, second_start_idx)]

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        
        # self.cache = [ [-1] * (len(text2) + 1) for _ in range(len(text1))]
        # for row in self.cache:
        #     row[-1] = 0
        # self.cache.append([ 0 ] * (len(text2) + 1))
        
        self.cache = [ [-1] * len(text2) for _ in range(len(text1))]
        
        def findSubsequence(idx1, idx2):
            if idx1 == len(text1) or idx2 == len(text2):
                return 0
            if self.cache[idx1][idx2] != -1:
                return self.cache[idx1][idx2]
            res = 0
            if text1[idx1] == text2[idx2]:
                res = 1 + findSubsequence(idx1 + 1, idx2 + 1)
            else:
                res = max(
                    findSubsequence(idx1 + 1, idx2),
                    findSubsequence(idx1, idx2 + 1)
                )
            self.cache[idx1][idx2] = res
            return res
        
        return findSubsequence(0, 0)


class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        #Bottom Up DP 
        if not text1 or not text2:
            return 0
        mem = [[0] * len(text2) for _ in range(len(text1))]
        if text1[0] == text2[0]:
            mem[0][0] = 1 
        for i in range(1,len(text1)):
            mem[i][0] = 1 if text1[i] == text2[0] else mem[i-1][0]
        for i in range(1,len(text2)):
            mem[0][i] = 1 if text2[i] == text1[0] else mem[0][i-1]
        for i in range(1, len(text1)):
            for j in range(1,len(text2)):
                if text1[i] == text2[j]:
                    mem[i][j] = max(mem[i-1][j-1]+1, mem[i][j-1], mem[i-1][j])
                else:
                    mem[i][j] = max(mem[i-1][j], mem[i][j-1])
        return mem[-1][-1]
                
        
        


from functools import lru_cache

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        self.text1, self.text2 = text1, text2
        return self.lcs(0, 0)
        
    @lru_cache(maxsize=None)
    def lcs(self, from1, from2):
        if from1 >= len(self.text1) or from2 >= len(self.text2): return 0 
        if self.text1[from1] == self.text2[from2]:
            return 1 + self.lcs(from1+1, from2+1)
        else:
            return max(self.lcs(from1, from2+1),
                       self.lcs(from1+1, from2))


from functools import lru_cache
class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        self.text1 = text1
        self.text2 = text2
        return self.solve(len(text1), len(text2))
    
    @lru_cache(None)
    def solve(self, m, n):
        if not m or not n:
            return 0
        
        if self.text1[m-1] == self.text2[n-1]:
            return 1 + self.solve(m-1, n-1)
        else:
            return max(self.solve(m-1, n), self.solve(m, n-1))


class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        
        @lru_cache(maxsize=None)
        
        def LCS(t1,t2):

            if(len(t1) == 0 or len(t2) == 0):
                return 0
            else:
                if(t1[-1] == t2[-1]):
                    return LCS(t1[0:-1],t2[0:-1]) + 1
                else:
                    return max(LCS(t1[0:-1],t2), LCS(t1,t2[0:-1]))     
        
        return LCS(text1,text2)

import numpy as np
class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        n = len(text1)
        m = len(text2)
        best = np.zeros((n+1,m+1))
        ans = 0
        for i in range(1,n+1):
            for j in range(1,m+1):
                
                if text1[i-1]==text2[j-1]:
                    best[i][j] = best[i-1][j-1] + 1
                else:
                    best[i][j] = max(best[i-1][j],best[i][j-1])
                    
                ans = max(ans,best[i][j])
                
        return int(ans)

import numpy as np

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        l1 = len(text1)
        l2 = len(text2)
        if l1 == l2 and text1 == text2:
            return l1
        if l1 < l2:
            text1, text2, l1, l2 = text2, text1, l2, l1
        mat_ = np.zeros((l2+1, l1+1))
        for j in range(1, l2+1):
            for i in range(1, l1+1):
                if text2[j-1] == text1[i-1]:
                    mat_[j, i] = 1 + mat_[j-1, i-1]
                else:
                    mat_[j, i] = max(mat_[j, max(0, i-1)], mat_[max(0, j-1), i])
        return int(mat_[-1][-1])


class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        m = len(text1)
        n = len(text2)
        dp = []
        for i in range(m+1):
            dp.append([0] * (n+1))
        for i in range(1, m+1):
            text1_sub = text1[:i]
            for j in range(1, n+1):
                ch = text2[j-1]
                options = [dp[i][j-1]]
                last_idx = i - text1_sub[::-1].find(ch) - 1
                if last_idx != i:
                    options.append(1 + dp[last_idx][j-1])
                dp[i][j] = max(options)
        return dp[m][n]

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        record = [[0 for _ in range(len(text2))] for _ in range(len(text1))]
        
        def f(s1, s2, i, j):
            if i>=len(s1) or j >=len(s2):
                return 0
            if record[i][j] > 0:
                return record[i][j]
            
            if s1[i] == s2[j]:
                #temp = max(1 + f(s1, s2, i+1, j+1), f(s1, s2, i, j+1), f(s1, s2, i+1, j))
                temp = 1 + f(s1, s2, i+1, j+1)
            else:
                temp = max(f(s1, s2, i, j+1), f(s1, s2, i+1, j))
            
            record[i][j] = temp
            return record[i][j]
        
        f(text1, text2, 0, 0)
        return record[0][0]

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        dp=[[-1]*(len(text2)+1) for i in range(len(text1)+1)]
        
        def LCS(s1,s2,n,m,dp):
            if n==0 or m==0:
                return 0
            if dp[n-1][m-1]!=-1:
                return dp[n-1][m-1]
            if s1[n-1]==s2[m-1]:
                dp[n-1][m-1]=1+LCS(s1,s2,n-1,m-1,dp)
                return dp[n-1][m-1]
            else:
                dp[n-1][m-1]=max(LCS(s1,s2,n-1,m,dp),LCS(s1,s2,n,m-1,dp))
                return dp[n-1][m-1]
            
    
    
        
        
        return (LCS(text1,text2,len(text1),len(text2),dp))
        


class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        m = [[0] * len(text2) for _ in range(len(text1))]
        
        if text1[0] == text2[0]:
            m[0][0] = 1
        
        for i in range(1, len(text1)):
            m[i][0] = 1 if text1[i] == text2[0] else m[i-1][0]
        for i in range(1, len(text2)):
            m[0][i] = 1 if text2[i] == text1[0] else m[0][i-1]
            
        for i in range(1, len(text1)):
            for j in range(1, len(text2)):
                if text1[i] == text2[j]:
                    m[i][j] = max(1 + m[i - 1][j - 1], m[i - 1][j], m[i][j - 1])
                else:
                    m[i][j] = max(m[i - 1][j], m[i][j - 1])
        return m[-1][-1]

from functools import lru_cache

class Solution:
    
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        
#         @lru_cache(maxsize=None)
#         def recurse(text1:str, text2:str) -> int:
            
#             if len(text1) == 0 or len(text2) == 0:
#                 return 0
            
#             if text1[0] == text2[0]:
#                 return 1+ recurse(text1[1:],text2[1:])
#             else:
#                 return max(recurse(text1,text2[1:]),recurse(text2,text1[1:]))
        
#         return recurse(text1,text2)
        
        @lru_cache(maxsize=None)
        def recursion(text1:str, text2:str) -> int:
            
            if len(text1) == 0 or len(text2) == 0:
                return 0
            
            if text1[0] == text2[0]:
                return 1 + recursion(text1[1:], text2[1:])
            
            else:
                return max(recursion(text1,text2[1:]), recursion(text1[1:], text2))
        
        return recursion(text1,text2)

from functools import lru_cache

class Solution:
    
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        
    
        @lru_cache(maxsize=None)
        def recursion(text1:str, text2:str) -> int:
            
            if len(text1) == 0 or len(text2) == 0:
                return 0
            
            if text1[0] == text2[0]:
                return 1 + recursion(text1[1:], text2[1:])
            
            else:
                return max(recursion(text1,text2[1:]), recursion(text1[1:], text2))
        
        return recursion(text1,text2)

from functools import lru_cache

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        @lru_cache(maxsize = None)
        def memo_solve(p1, p2):
            if len(text1) == p1 or len(text2) == p2:
                return 0
            
            if text1[p1] == text2[p2]:
                return 1 + memo_solve(p1 + 1, p2 + 1)
            else:
                return max(memo_solve(p1, p2 + 1), memo_solve(p1 + 1, p2))
        return memo_solve(0, 0)
        
        
#         @lru_cache(maxsize = None)
#         def memo_solve(p1, p2):
#             if len(text1) == p1 or len(text2) == p2:
#                 return 0
            
#             option_1 = memo_solve(p1 + 1, p2)
            
#             first_occurence = text2.find(text1[p1], p2)
#             option_2 = 0
#             if first_occurence != -1:
#                 option_2 = 1 + memo_solve(p1 + 1, first_occurence + 1)
            
#             return max(option_1, option_2)
        
#         return memo_solve(0, 0)


from functools import lru_cache

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        n1 = len(text1)
        n2 = len(text2)
        
        @lru_cache(None)
        def dp(s1, s2):
            if len(s1) == 0 or len(s2) == 0:
                return 0
            elif s1[0] == s2[0]:
                return 1 + dp(s1[1:], s2[1:])
            return max(dp(s1[1:], s2), dp(s1, s2[1:]))
        
        return dp(text1, text2)


import numpy as np
from functools import lru_cache
class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        if len(text1) == 0 or len(text2) == 0:
            return 0
        
        m = len(text1)
        n = len(text2)
        return self.dp(text1, text2, m-1, n-1)
        
#         A = np.zeros((m+1, n+1),int)
        
#         for i in range(1,m+1):
#             for j in range(1,n+1):
#                 if text1[i-1] == text2[j-1]:
#                     A[i,j] = A[i-1,j-1] +1
#                 else:
#                     A[i,j] = max(A[i-1,j], A[i,j-1])
#         return A[-1,-1]
        
    @lru_cache(maxsize=None)
    def dp(self, text1, text2, i, j):
        if i  < 0 or j < 0:
            return 0
        if text1[i] == text2[j]:
            return self.dp(text1, text2, i-1, j-1) + 1
        else:
            return max(self.dp(text1, text2, i-1, j), self.dp(text1, text2, i, j-1))

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        @lru_cache(maxsize=None)
        def memo_solve(p1, p2):
            if p1==len(text1) or p2==len(text2):
                return 0
            
            case1=memo_solve(p1+1, p2)
            first = text2.find(text1[p1], p2)
            case2=0
            if first != -1:
                case2 = 1 + memo_solve(p1+1, first +1)
            
            return max(case1, case2)
        return memo_solve(0, 0)


class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        
        @lru_cache(maxsize=None)
        def memo_solve(p1, p2):
            
            # Base case: If either string is now empty, we can't match
            # up anymore characters.
            if p1 == len(text1) or p2 == len(text2):
                return 0
            
            # Option 1: We don't include text1[p1] in the solution.
            option_1 = memo_solve(p1 + 1, p2)
            
            # Option 2: We include text1[p1] in the solution, as long as
            # a match for it in text2 at or after p2 exists.
            first_occurence = text2.find(text1[p1], p2)
            option_2 = 0
            if first_occurence != -1:
                option_2 = 1 + memo_solve(p1 + 1, first_occurence + 1)
            
            # Return the best option.
            return max(option_1, option_2)
                
        return memo_solve(0, 0)

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        memo = [[0]*(len(text2)+1) for i in range(len(text1)+1)]
        s1=text1
        s2=text2
        def helper(i1,i2):
            if memo[i1][i2]:
                return memo[i1][i2]
            if i1 == len(s1) or i2 == len(s2):
                return 0
            if s1[i1] == s2[i2]:
                memo[i1][i2] = 1+helper(i1+1,i2+1)
                
            else:
                memo[i1][i2] =  max(helper(i1+1,i2),helper(i1,i2+1))
            return memo[i1][i2]
            
        
        
        
        
        
        
        return helper(0,0)

from functools import lru_cache


class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        '''
        base case:
        text1 = c1, text2 = c2
        if c1 == c2 return 1, if c1 != c2 return 0
        text1 = sub1 + c1 -> c1 is the last char
        text2 = sub2 + c2
        
        DP(text1, text2) = max(DP(text1, sub2), DP(sub1, text2), DP(sub1, sub2))
                           or DP(sub1, sub2) + 1 if c1 == c2
        '''
        if len(text1) == 0 or len(text2) == 0:
            return 0
        
        @lru_cache(None)
        def lcs_of_sub(s1, s2):
            if not s1 or not s2:
                return 0
            c1, c2 = s1[-1], s2[-1]
            sub1, sub2 = s1[:-1], s2[:-1]
            # print(sub1, c1, sub2, c2)
            if c1 == c2:
                return lcs_of_sub(sub1, sub2) + 1
            return max(
                lcs_of_sub(sub1, sub2), lcs_of_sub(sub1, s2), lcs_of_sub(s1, sub2)
            )
        
        return lcs_of_sub(text1, text2)

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        memo={}
        def LCS(s1,s2, i1, i2):
            if i1>len(s1)-1 or i2>len(s2)-1: return 0
            if (i1,i2) in memo: return memo[(i1,i2)]
            if s1[i1]==s2[i2]:
                memo[(i1,i2)]=1+ LCS(s1,s2,i1+1,i2+1)
                return memo[(i1,i2)]
            s1_next=LCS(s1,s2,i1+1,i2)
            s2_next=LCS(s1,s2,i1,i2+1)
            memo[(i1,i2)]= max(s1_next,s2_next)
            return memo[(i1,i2)]
        
        return LCS(text1,text2,0,0)
                    
                
    
    
    
    


class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        
        memo = [[None for i in range(len(text2)+1)] for _ in range(len(text1)+1)]
        def rec(i, j):
            if i == len(text1) or j == len(text2):
                return 0
            
            if text1[i] == text2[j]:
                if not memo[i+1][j+1]:
                    memo[i+1][j+1] = rec(i+1, j+1)
                return 1 + memo[i+1][j+1]
            else:
                if not memo[i][j+1]:
                    memo[i][j+1] = rec(i, j+1)
                if not memo[i+1][j]:
                    memo[i+1][j] = rec(i+1, j)
                return max(memo[i][j+1], memo[i+1][j])
            
        return rec(0, 0)

class Solution:
    def __init__(self):
        self.cached = {}
        
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        if len(text1) == 0 or len(text2) == 0:
            return 0
        
        
        if (len(text1), len(text2)) in self.cached:
            return self.cached[(len(text1), len(text2))]
        
        if text1[-1] == text2[-1]:
            r = self.longestCommonSubsequence(text1[:-1], text2[:-1]) + 1
        else:
            r = max(
                self.longestCommonSubsequence(text1, text2[:-1]),
                self.longestCommonSubsequence(text1[:-1], text2)
            )
        
        self.cached[(len(text1), len(text2))] = r
        
        return r


class Solution:
    @lru_cache(maxsize = None)
    def longest(self, p1, p2):
        if p1 == len(self.t1) or p2 == len(self.t2):
            return 0
        
        if self.t1[p1] == self.t2[p2]:
            return 1 + self.longest(p1 + 1, p2 + 1)
        
        return max(self.longest(p1 + 1, p2), self.longest(p1, p2 + 1))
    
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        self.t1 = text1
        self.t2 = text2
        return self.longest(0, 0)

class Solution:
    def longestCommonSubsequence(self, str1: str, str2: str) -> int:
    
        cache = [ [-1]*len(str2) for _ in str1]

        
        def checkPosition(i1, i2):
            
            if i1 == len(str1) or i2 == len(str2):
                return 0
            
            #hashing
            if cache[i1][i2] != -1:
                return cache[i1][i2]

            # the characters match, so we can keep both
            if str1[i1] == str2[i2]:
                keep = 1 + checkPosition(i1+1, i2+1)

            else: 
                keep = -1

            skip1 = checkPosition(i1+1, i2)
            skip2 = checkPosition(i1, i2+1)
            
            best = max([keep, skip1, skip2])
            cache[i1][i2] = best
            return best

        return checkPosition(0,0)
    
    



class Solution:
    
    def _longest_common_subsequence(self, s1, s2, cache):
        if (s1, s2) in cache:
            return cache[(s1, s2)]
        elif len(s1) == 0 or len(s2) == 0:
            cache[(s1, s2)] = 0
            return 0
        elif s1[-1] == s2[-1]:
            answer = 1 + self._longest_common_subsequence(s1[:-1], s2[:-1], cache)
            cache[(s1, s2)] = answer
            return answer
        else:
            answer = max(self._longest_common_subsequence(s1, s2[:-1], cache), self._longest_common_subsequence(s1[:-1], s2, cache))
            cache[(s1, s2)] = answer
            return answer
    
    def longestCommonSubsequence(self, s1: str, s2: str) -> int:
        return self._longest_common_subsequence(s1, s2, {})

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        def lcs(i,j):
            if i==len(text1) or j==len(text2):
                return 0
            if tuple([i,j]) in dp:
                return dp[tuple([i,j])]
            if text1[i]==text2[j]:
                dp[tuple([i,j])]=1+lcs(i+1,j+1)
                return dp[tuple([i,j])]
            dp[tuple([i,j])]=max(lcs(i+1,j),lcs(i,j+1))
            return dp[tuple([i,j])]
        dp={}
        # text1+=\"0\"
        # text2+=\"0\"
        return lcs(0,0)

class Solution:
    def longestCommonSubsequence(self, s1: str, s2: str) -> int:
        def rec(s1, s2, i, j, lcs):
            if i == len(s1) or j == len(s2):
                return 0
            if (i, j) in lcs:
                return lcs[(i, j)]
            else:
                if s1[i] == s2[j]:
                    lcs[(i, j)] = 1 + rec(s1, s2, i + 1, j + 1, lcs)
                else:
                    l = rec(s1, s2, i + 1, j, lcs)
                    r = rec(s1, s2, i, j + 1, lcs)
                    lcs[(i, j)] = max(l, r)
                return lcs[(i, j)]
        return rec(s1, s2, 0, 0, {})

class Solution:
    # def longestCommonSubsequence(self, text1: str, text2: str) -> int:
    #     matrix = [[None]*(len(text2)+1) for i in range(len(text1)+1)]
    #     for j in range(len(text2)+1):
    #         matrix[0][j] = 0
    #     for i in range(len(text1)+1):
    #         matrix[i][0] = 0
    #     for i in range(1, len(text1)+1):
    #         for j in range(1, len(text2)+1):
    #             if text1[i-1] == text2[j-1]:
    #                 matrix[i][j] = 1 + matrix[i-1][j-1]
    #             else:
    #                 matrix[i][j] = max(matrix[i-1][j], matrix[i][j-1])
    #     return matrix[len(text1)][len(text2)]
    
    
    def _longest_common_subsequence(self, s1, s2, cache):
        if (s1, s2) in cache:
            return cache[(s1, s2)]
        elif len(s1) == 0 or len(s2) == 0:
            return 0
        elif s1[-1] == s2[-1]:
            answer = 1 + self._longest_common_subsequence(s1[:-1], s2[:-1], cache)
            cache[(s1, s2)] = answer
            return answer
        else:
            answer = max(self._longest_common_subsequence(s1, s2[:-1], cache), self._longest_common_subsequence(s1[:-1], s2, cache))
            cache[(s1, s2)] = answer
            return answer

    def longestCommonSubsequence(self, s1, s2):
        return self._longest_common_subsequence(s1, s2, {})

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        memo = [[ -1 for i in range(len(text2))] for i in range (len(text1))]
        
        def memoSolve(i, j) :
            if i == len(text1) or j == len(text2):
                return 0
            
            if memo[i][j] >= 0:
                return memo[i][j]
            
            includeHere = 0
            if (text1[i] == text2[j]):
                includeHere = 1 + memoSolve(i + 1, j + 1)
            includeLater = memoSolve(i, j+1)
            included = max(includeHere, includeLater)
            noTake = max(memoSolve(i + 1, j), memoSolve(i+1, j+1))
            
            memo[i][j] = max(included, noTake)
            return memo[i][j]
            
        return memoSolve(0,0)

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        
        @lru_cache(maxsize=None)
        def memo_solve(p1, p2):
            
            # Base case: If either string is now empty, we can't match
            # up anymore characters.
            if p1 == len(text1) or p2 == len(text2):
                return 0
            
            # Option 1: We don't include text1[p1] in the solution.
            option_1 = memo_solve(p1 + 1, p2)
            
            # Option 2: We include text1[p1] in the solution, as long as
            # a match for it in text2 at or after p2 exists.
            first_occurence = text2.find(text1[p1], p2)
            option_2 = 0
            if first_occurence != -1:
                option_2 = 1 + memo_solve(p1 + 1, first_occurence + 1)
            
            # Return the best option.
            return max(option_1, option_2)
                
        return memo_solve(0, 0)    

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        # dp[i][j] = dp[i-1][j-1] + 1 if text1[i] == text2[j]
        # else max(dp[i-1][j], dp[i][j-1])
        m, n = len(text1), len(text2)
        dp = [[0]*(n+1) for _ in range(m+1)]
        for i in range(1, m+1):
            for j in range(1, n+1):
                if text1[i-1] == text2[j-1]:
                    dp[i][j] = dp[i-1][j-1] + 1
                else:
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])
        return dp[-1][-1]

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        memo = [[0]*len(text2) for i in range(len(text1))]
        def helper(s1,s2,i1,i2):
            if not s1 or not s2:
                return 0
            if memo[i1][i2]:
                return memo[i1][i2]
            if s1[0] == s2[0]:
                memo[i1][i2] = 1+helper(s1[1:],s2[1:],i1+1,i2+1)
                
            else:
                memo[i1][i2] =  max(helper(s1[1:],s2,i1+1,i2),helper(s1,s2[1:],i1,i2+1))
            return memo[i1][i2]
            
        
        
        
        
        
        
        return helper(text1,text2,0,0)

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        n, m = len(text1), len(text2)
        dp = [[0] * (m + 1) for _ in range(n + 1)]
        for row in range(1, n + 1):
            for col in range(1, m + 1):
                if text1[row - 1] == text2[col - 1]:
                    dp[row][col] = 1 + dp[row - 1][col - 1]
                else:
                    dp[row][col] = max(dp[row - 1][col], dp[row][col - 1])
        return dp[n][m]
    
    def longestCommonSubsequence1(self, text1: str, text2: str) -> int:
        def helper(i1, i2):
            if (i1, i2) in self.memo:
                return self.memo[(i1, i2)]
            
            res = 0
            if i1 == len(text1) or i2 == len(text2):
                res = 0
            elif text1[i1] == text2[i2]:
                res = 1 + helper(i1 + 1, i2 + 1)
            else:
                res = max(helper(i1 + 1, i2), helper(i1, i2 + 1))
            
            self.memo[(i1, i2)] = res
            return self.memo[(i1, i2)]
        
        self.memo = {}
        return helper(0, 0)

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        n,m=len(text1),len(text2)
        dp=[[0]*(m+1) for _ in range(n+1)]
        for i in range(n):
            for j in range(m):
                if text1[i]==text2[j]:
                    dp[i+1][j+1]=dp[i][j]+1
                else:
                    dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j])
        return dp[-1][-1]

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        
        
        dp=[[0]*(len(text2)+1) for _ in range(len(text1)+1)]
        
        for i in range(1,len(dp)):
            for j in range(1,len(dp[0])):
                
                if text1[i-1]==text2[j-1]:
                    dp[i][j]=dp[i-1][j-1]+1
                else:
                    dp[i][j]=max(dp[i-1][j],dp[i][j-1])
                
                
        return dp[-1][-1]


class Solution:
    def helper(self, text1, text2, index1, index2, match):
        if index1 == len(text1) or index2 == len(text2):
            return match
        s1 = 0
        s2 = 0
        s3 = 0
        # case - match
        if text1[index1] == text2[index2]:
            s1 = self.helper(text1, text2, index1+1, index2+1, match+1)
        else:
            # case - did not match
            s2 = self.helper(text1, text2, index1, index2+1, match)
            s3 = self.helper(text1, text2, index1+1, index2, match)
            
        return max(s1, s2, s3)
        
    
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        
        if not text1 or not text2:
            return 0
        
        dp = [[0 for i in range(len(text1)+1)] for j in range(len(text2)+1)]
        
        for i in range(1, len(dp)):
            for j in range(1, len(dp[0])):
                
                if text1[j-1] == text2[i-1]:
                    dp[i][j] = 1 + dp[i-1][j-1]
                else:
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])
                    
        return dp[len(text2)][len(text1)]


class Solution:
    def longestCommonSubsequence(self, stringA: str, stringB: str) -> int:
        lengthA = len(stringA)
        lengthB = len(stringB)
        dp = [[ 0 for j in range(lengthB + 1)] for i in range(lengthA + 1)]
        for i in range(1, lengthA + 1):
            for j in range(1, lengthB + 1):
                if stringA[i - 1] == stringB[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1] + 1
                else:
                    dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])
        return dp[lengthA][lengthB]


class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        
        len1 = len(text1)
        len2 = len(text2)
        
        dp = [[0 for _ in range(len2+1)] for _ in range(len1+1)]
        
        for i in range(len1):
            for j in range(len2):
                if text1[i] == text2[j]:
                    dp[i+1][j+1] = dp[i][j]+1
                else:
                    dp[i+1][j+1] =  max(dp[i][j+1],dp[i+1][j])
                    
        
        return dp[len1][len2]


class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        # use dynamic programming
        
        # initialize table to store sub solutions
        # row (i) = index of text1 + 0 for initial row
        # column (j) = index of text2 + 0 for initial row
        # cell = max length of subsequence for text1[1:i] text2[1:j]
        t = [[0 for _ in range(len(text2)+1)] for _ in range(len(text1)+1)]
        
        
        # loop through each element
        for i in range(1, len(text1)+1):
            for j in range(1, len(text2)+1):
                # if text is the same, diagonal cell + 1
                if text1[i-1] == text2[j-1]:
                    t[i][j] = t[i-1][j-1] + 1
                # else, max of above (not considering last of text 1) or left
                else:
                    t[i][j] = max(t[i-1][j], t[i][j-1])
        
        # return right bottom of table
        return t[len(text1)][len(text2)]        


class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        if not text1 or not text2:
            return 0
        m, n = len(text1), len(text2)
        dp = [[0 for _ in range(n+1)] for _ in range(m+1)]
        for i in range(1, m+1):
            for j in range(1, n+1):
                if text1[i-1] == text2[j-1]:
                    dp[i][j] = dp[i-1][j-1] + 1
                else:
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])
        return dp[m][n]



class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        # dp
        if not text1 or not text2:
            return 0
        m, n = len(text1), len(text2)
        dp = [[0 for _ in range(n+1)] for _ in range(m+1)]
        for i in range(1, m+1):
            for j in range(1, n+1):
                if text1[i-1] == text2[j-1]:
                    dp[i][j] = dp[i-1][j-1] + 1
                else:
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])
        return dp[m][n]


class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        
        
        row = len(text1) + 1
        col = len(text2) + 1
        
        
        dp = [[0 for _ in range(col)] for _ in range(row)]
        
        for i in range(1,row):
            for j in range(1,col):
                
                if(text1[i-1] == text2[j-1]):
                    dp[i][j] = dp[i-1][j-1] + 1
                else:
                    dp[i][j] = max(dp[i-1][j],dp[i][j-1])
                    
        
        return dp[-1][-1]


class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        ans = 0
        dp = [[0 for _ in range(len(text1)+1)] for _ in range(len(text2)+1)]
        
        for i in range(1, len(text2)+1):
            for j in range(1, len(text1)+1):
                if text2[i-1] == text1[j-1]:
                    dp[i][j] = dp[i-1][j-1]+1
                else:
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])
            ans = max(ans, dp[i][j])
        return ans
      


class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        dp = [[0 for _ in range(len(text2) + 1)] for _ in range(len(text1) + 1)]
        
        for i in range(1, len(text1) + 1):
            for j in range(1, len(text2) + 1):
                if text1[i - 1] == text2[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1] + 1
                else:
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
        return dp[-1][-1]


class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        L1=len(text1)
        L2=len(text2)
        A=[ [0]*(L2+1) for i in range(L1+1)]

        ##print(A)
        Max=0
        ##print(L1,L2)
        for i in range(L1,-1,-1):
                for j in range(L2,-1,-1):
                    if i<L1 and j<L2:
                        ##print(i,j)
                        if text1[i]==text2[j]:
                                A[i][j]= A[i+1][j+1]+1
                        else: A[i][j]=max(A[i][j+1],A[i+1][j])
                    if Max<A[i][j]: Max=A[i][j]


        ##print(A[2][3])
        return A[i][j]
    
        
        
        


class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        s1=text1
        s2=text2
        if len(s1)==0 or len(s2)==0:
            return 0
        rows,cols=len(s1)+1,len(s2)+1
        arr = [[0 for i in range(cols)] for j in range(rows)] 
        for i in range(len(s1)):
            for j in range(len(s2)):
                if s1[i]==s2[j]:
                    arr[i][j]=arr[i-1][j-1]+1
                if s1[i]!=s2[j]:
                    arr[i][j]=max(arr[i-1][j],arr[i][j-1])
        return (arr[rows-2][cols-2])


class Solution:
    def longestCommonSubsequence(self, A: str, B: str) -> int:
        m,n = len(A), len(B)
        dp = [[0]*(n+1) for i in range(m+1)]
        for i in range(m+1):
            for j in range(n+1):
                if i==0 or j==0:
                    dp[i][j] =0
                elif A[i-1] == B[j-1]:
                    dp[i][j] = 1+dp[i-1][j-1]
                else:
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1] )
        return dp[m][n]


class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        dp = [0]*(len(text2)+1)
        for i in range(1, len(text1)+1):
            prev = dp[0]
            for j in range(1, len(text2)+1):
                last = dp[j]
                if text1[i-1]==text2[j-1]:
                    dp[j] = prev+1
                if last>prev:
                    prev = last
        return max(dp)

class Solution:
    def longestCommonSubsequence(self, s1: str, s2: str) -> int:
        
        #注意这里不要写成【0 * （len....）】
        dp_grid = [[0] * (len(s1) + 1) for _ in range(len(s2) + 1)]
        
        for r in range(len(s2) + 1):
            for c in range(len(s1) + 1):
                
                if r == 0 or c == 0: 
                    dp_grid[r][c] = 0
                    
                #注意这里的s2和s1是string,别搞错写成s2[r-1][c-1]了
                elif s2[r-1] == s1[c-1]:
                    dp_grid[r][c] = dp_grid[r-1][c-1] + 1
                
                else:
                    dp_grid[r][c] = max(dp_grid[r-1][c], dp_grid[r][c-1])
                
        return dp_grid[-1][-1]
    
                    


class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        
        if not text1 or not text2: return 0
        dp = [[0 for i in range(len(text1))] for j in range(len(text2))]
        for i in range(len(text2)):
            for j in range(len(text1)):
                if i == 0 and j == 0:
                    dp[i][j] = 1 if text1[j] == text2[i] else 0
                elif i == 0:
                    if dp[i][j-1] == 0 and text1[j] == text2[i]: dp[i][j] = 1
                    else: dp[i][j] = dp[i][j-1]
                elif j == 0:
                    dp[i][j] = 1 if dp[i-1][j] == 1 or text1[j] == text2[i] else 0
                elif text1[j] == text2[i]:
                    dp[i][j] = 1 + dp[i-1][j-1]
                else:
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])
        return dp[-1][-1]

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:    
        def lcsTab(s1,s2,m,n):
            dp = [[0 for i in range(n+1)] for j in range(m+1)]
            
            for i in range(m+1):
                for j in range(n+1):
                    if(i==0 or j==0):
                        dp[i][j] = 0
                    elif(s1[i-1] == s2[j-1]):
                        dp[i][j] = 1+dp[i-1][j-1]
                    else:
                        dp[i][j] = max(dp[i-1][j],dp[i][j-1])
            
            return dp[m][n]
            
        m = len(text1)
        n = len(text2)
        
        return lcsTab(text1,text2,m,n)
        


class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        n=len(text1)
        m=len(text2)
        dp=[[0 for i in range(m+1)] for i in range(n+1)]
        
        for i in range(1,n+1):
            for j in range(1,m+1):
                
                if text1[i-1] == text2[j-1]:
                    dp[i][j]=1+dp[i-1][j-1]
                    
                else:
                    dp[i][j]=max(dp[i-1][j],dp[i][j-1])
        print(dp)            
        return dp[n][m]           


class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        
        dynamic_array = [[0 for c in range(len(text2)+1)] for ch in range(len(text1)+1)]
        
        
        for i in range(len(text1)+1):
            for j in range(len(text2)+1):
                
                if i == 0 or j == 0:
                    dynamic_array[i][j] = 0
                elif text1[i-1] == text2[j-1]:
                    dynamic_array[i][j] = 1 + dynamic_array[i-1][j-1]
                else:
                    dynamic_array[i][j] = max(dynamic_array[i-1][j],dynamic_array[i][j-1])
        
        return dynamic_array[len(text1)][len(text2)]
        
        


class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        l1 = len(text1)
        l2 = len(text2)
        dp = [[0 for c in range(l2+1)] for r in range(l1+1)]
        
        for i in range(l1):
            for j in range(l2):                
                dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1], dp[i][j] + (text1[i]==text2[j]))
        return dp[-1][-1]


class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        dp = [[0 for i in range(len(text1)+1)] for j in range(len(text2)+1)]
        for i in range(1, len(text2)+1):
            for j in range(1, len(text1)+1):
                if text2[i-1] == text1[j-1]:
                    dp[i][j] = 1 + dp[i-1][j-1]
                else:
                    dp[i][j] = max(dp[i][j-1], dp[i-1][j])
        print(dp)
        return dp[-1][-1]


class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        dp=[[-1 for i in range(len(text2)+1)]for j in range(len(text1)+1)]
        for i in range(len(text1)+1):
            for j in range(len(text2)+1):
                if i==0 or j==0:
                    dp[i][j]=0
        for i in range(1,len(text1)+1):
            for j in range(1,len(text2)+1):
                if text1[i-1]==text2[j-1]:
                    dp[i][j]=dp[i-1][j-1]+1
                else:
                    dp[i][j]=max(dp[i-1][j],dp[i][j-1])
        return dp[len(text1)][len(text2)]

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        l1, l2 = len(text1), len(text2)
        if l1 == 0 or l2 == 0:
            return 0
        dp = [0 for _ in range(l1+1)]
        for i in range(l2):
            temp = [n for n in dp]
            curMax = 0
            for j in range(1, l1+1):
                if temp[j-1] > curMax:
                    curMax = temp[j-1]
                if text2[i] == text1[j-1]:
                    dp[j] = curMax + 1
            
        return max(dp)
        


class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        L1 = len(text1)
        L2 = len(text2)
        dp = [[0 for _ in range(L2 + 1)] for _ in range(L1 + 1)]
        
        for i in range(1, L1 + 1):
            for j in range(1, L2 + 1):
                if text1[i - 1] == text2[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1] + 1
                else:
                    dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1])
        
        return dp[-1][-1]

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        
        
        dp = [[0 for j in range(len(text2))] for i in range(len(text1))]
        
        for i in range(len(text1)):
            for j in range(len(text2)):
                if text1[i] == text2[j]:
                    if not i or not j:
                        dp[i][j] = 1
                    else:
                        dp[i][j] = dp[i-1][j-1] + 1
                else:
                    if i:
                        dp[i][j] = dp[i-1][j]
                    if j:
                        dp[i][j] = max(dp[i][j],dp[i][j-1])
                        
        return dp[-1][-1]

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        s1=text1
        s2=text2
        if len(s1)==0 or len(s2)==0:
            return 0
        rows=len(s1)+1
        cols=len(s2)+1
        arr=[[0 for i in range(cols)] for j in range(rows)]
        for i in range(len(s1)):
            for j in range(len(s2)):
                if s1[i]==s2[j]:
                    arr[i+1][j+1]=arr[i][j]+1
                if s1[i]!=s2[j]:
                    arr[i+1][j+1]=max(arr[i][j+1],arr[i+1][j])
        return(arr[-1][-1])


class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        n,m=len(text1),len(text2)
        dp = [[0 for i in range(m+1)] for j in range(n+1)]
        for i in range(1,n+1):
            for j in range(1,m+1):
                if text1[i-1]==text2[j-1]:
                    dp[i][j]=dp[i-1][j-1]+1
                else:
                    dp[i][j]=max(dp[i-1][j],dp[i][j-1])
        return dp[n][m]

class Solution:
    def longestCommonSubsequence(self, a: str, b: str) -> int:
        m, n = len(a), len(b)
        dp = [[0 for _ in range(n)] for _ in range(m)]
        for i in range(m):
            for j in range(n):
                if a[i] == b[j]:
                    dp[i][j] = 1 + (dp[i - 1][j - 1] if i - 1 >= 0 and j - 1 >= 0 else 0)
                else:
                    dp[i][j] = max(dp[i][j - 1] if j - 1 >= 0 else 0, dp[i - 1][j] if i - 1 >= 0 else 0)
        print(dp)
        return dp[-1][-1]

class Solution:
    
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        ## recurrsion => lead to time exceeded
        # if not text1 or not text2:
        #     return 0            
        # if text1[-1]==text2[-1]:
        #     return 1+self.longestCommonSubsequence(text1[0:-1],text2[0:-1])
        # elif text1[-1] != text2[-1]:
        #     t1 = self.longestCommonSubsequence(text1,text2[0:-1])
        #     t2 = self.longestCommonSubsequence(text1[0:-1],text2)
        #     return max(t1,t2)
        ## memorized method 
#         n = len(text1)
#         m = len(text2)
#         arr = [[0] * (m+1) for _ in range(n+1)]
#         return self.LCS(text1,text2,n,m,arr)
        
#     def LCS(self,text1,text2,n,m,arr):
#         if arr[n][m]:
#             return arr[n][m]
#         if n==0 or m==0:
#             res = 0
#         elif text1[n-1]==text2[m-1]:
#             res = 1+self.LCS(text1,text2,n-1,m-1,arr)
#         else:
#             t1 = self.LCS(text1,text2,n,m-1,arr)
#             t2 = self.LCS(text1,text2,n-1,m,arr)
#             res = max(t1,t2)
#         arr[n][m] = res
#         return res
        # bottom-up method
        n,m = len(text1), len(text2)
        arr = [[0]*(m+1) for _ in range(n+1)]
        for i in range(n+1):
            for j in range(m+1):
                if i==0 or j==0:
                    arr[i][j] = 0
                elif text1[i-1]==text2[j-1]:
                    arr[i][j] = 1 + arr[i-1][j-1]
                else:
                    arr[i][j] = max(arr[i-1][j],arr[i][j-1])
        return arr[-1][-1] # arr[-1][-1]


class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        
        d = [[None] * (len(text2)+1) for _ in range(len(text1)+1)] 
        for j in range(len(text2)+1):
            d[0][j] = 0
        for i in range(len(text1)+1):
            d[i][0] = 0
        i = 1
        while i < len(text1) + 1:
            j = 1
            while j < len(text2) + 1:
                if text1[i-1] == text2[j-1]:
                    d[i][j] = max(d[i-1][j-1] + 1, d[i][j-1], d[i-1][j])
                else:
                    d[i][j] = max(d[i][j-1], d[i-1][j])
                j += 1
            i += 1
        return max([max(row) for row in d])
            


class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        
        table={}
        def helper(t1, t2, i,j, table):
            if table.get((i,j)) != None:
                return table[(i,j)]
            
            n = len(t1)
            m = len(t2)
            
            if m <=j or n <= i:
                return 0;     
            
            v = t1[i]
            idx = t2.find(v, j)
            if idx != -1:
                r = max(helper(t1, t2, i+1, j, table), helper(t1, t2, i+1, idx+1, table)+1)
                table[(i,j)] = r 
            else:
                r = helper(t1, t2, i+1,j, table)
                table[(i,j)] = r
            return table[(i,j)]
        
        return helper(text1, text2, 0, 0, table)
    
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        n = len(text1)
        m = len(text2)
        
        dp=[]
        for v in range(n+1):
            dp.append([-1]*(m+1))
        
        dp[0][0] = 0
        for i in range(n+1):
            dp[i][0] = 0
        for j in range(m+1):
            dp[0][j] = 0
        for i in range(1,n+1):
            for j in range(1, m+1):
                v1=text1[i-1]
                v2 = text2[j-1]
                if v1 == v2:
                    dp[i][j] = max(dp[i-1][j-1]+1, dp[i-1][j], dp[i][j-1])
                else:
                    dp[i][j] = max(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])
        return dp[n][m]


class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        
        if not text1 or not text2:
            return 0
        
        dp = [[0 for col in range(len(text2)+1)] for row in range(len(text1)+1)]
        
        for i in range(1,len(text1)+1):
            for j in range(1,len(text2)+1):
                options = [dp[i][j-1],dp[i-1][j]]
                if text1[i-1] == text2[j-1]:
                    options.append(dp[i-1][j-1]+1)
                dp[i][j] = max(options)
        return dp[-1][-1]

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        ################
        dp = [0]*(len(text2)+1)
        for i in range(1, len(text1)+1):
            prev = dp[0]
            for j in range(1, len(text2)+1):
                last = dp[j]
                if text1[i-1]==text2[j-1]:
                    dp[j] = prev+1
                if last>prev:
                    prev = last
        return max(dp)

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        m = len(text1)
        n = len(text2)
        memo = [[0 for _ in range(m)] for _ in range(n)]
        res = 0
        for row in range(n):
            if row == 0 and text2[row] == text1[0]:
                memo[row][0] = 1
            else:
                memo[row][0] = memo[row-1][0]
            
                if text2[row] == text1[0]:
                    memo[row][0] = 1
       
        
        for col in range(m):
            if col == 0 and text1[col] == text2[0]:
                memo[0][col] = 1
            else:
                memo[0][col] = memo[0][col-1]
            
                if text1[col] == text2[0]:
                    memo[0][col] = 1
        print(memo)
        for row in range(1, n):
            for col in range(1, m):
                if text1[col] != text2[row]:
                    memo[row][col] = max(memo[row-1][col],
                                         memo[row][col-1],
                                         memo[row-1][col-1])
                else:
                    memo[row][col] = 1 + min(memo[row-1][col],
                                         memo[row][col-1],
                                         memo[row-1][col-1])
        
        return memo[-1][-1]
                
        


class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        width,depth = len(text1),len(text2)
        dp = [[0 for _ in range(width)] for _ in range(depth)]
        for i in range(depth):
            for j in range(width):
                if i == 0 and j == 0:
                    dp[i][j] = 0
                if i == 0:
                    up = 0
                else:
                    up = dp[i-1][j]
                if j == 0:
                    left = 0
                else:
                    left = dp[i][j - 1]
                if (text2[i] == text1[j]):
                    if i == 0 or j == 0:
                        dp[i][j] = 1
                    else:
                        dp[i][j] = dp[i-1][j-1] + 1
                else:
                    dp[i][j] = max(left,up)
        for d in dp:print(d)
        return dp[-1][-1]

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        # dp[i][j]
        # represents what is the maximum up to that i and j included
        dp = [[0] * (len(text2) + 1) for _ in range(len(text1) + 1)]
        max_ = 0
        for i in range(len(text1)-1, -1, -1):
            for j in range(len(text2)-1, -1, -1):
                dp[i][j] = max(dp[i+1][j], dp[i][j+1])
                if text1[i] == text2[j]:
                    dp[i][j] = max(dp[i+1][j+1] + 1, dp[i][j])
                max_ = max(max_, dp[i][j])
        return max_

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        dp= [[0]*(len(text2)+1) for _ in range((len(text1)+1))]
        count=0
        for r in range(1, len(dp)):
            for c in range(1, len(dp[0])):
                if text1[r-1]==text2[c-1]:
                    dp[r][c]= dp[r-1][c-1]+1
                else:
                    dp[r][c]= max(dp[r-1][c], dp[r][c-1])
                    
                count= max(count,dp[r][c])
                
        return count


class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        n = len(text1)
        m = len(text2)
        dp = [[0 for _ in range(m)] for _ in range(n)]
        
        #i -> text2
        #j -> text1
        for i in range(n):
            for j in range(m):
                # Need to do j-1, i-1, otherwise we would start from 1
                # on both strings
                if text1[i] == text2[j]:
                    dp[i][j] = 1 + (0 if i-1 < 0 or j-1 < 0 else dp[i-1][j-1])
                else:
                    if i-1 > -1:
                        dp[i][j] = dp[i-1][j]
                    if j-1 > -1:
                        dp[i][j] = max(dp[i][j], dp[i][j-1])

        return dp[-1][-1]


class Solution:
    def longestCommonSubsequence(self, a: str, b: str) -> int:
        m, n = len(a), len(b)
        c = [[0 for _ in range(n + 1)] for _ in range(m + 1)]
        for i in range(m + 1):
            for j in range(n + 1):
                if i == 0 or j == 0: c[i][j] = 0
                else:
                    if a[i - 1] == b[j - 1]: c[i][j] = max([c[i - 1][j], c[i][j - 1], c[i - 1][j - 1] + 1])
                    else: c[i][j] = max([c[i - 1][j], c[i][j - 1]])
        return c[m][n]


class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        s1, s2 = len(text1), len(text2)
        # init 
        res = 0
        dp = [[0 for _ in range(s2+1)] for _ in range(s1+1)]
        # dp[i][j] = dp[i-1][j-1] + 1 if text1[i]==text2[j] 
        #            dp[i-1][j-1]      else 

        for i in range(1, s1+1):
            for j in range(1, s2+1):
                if text1[i-1]==text2[j-1]:
                    dp[i][j] = dp[i-1][j-1] + 1
                else:
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])
                res = max(dp[i][j], res)
        return res
        # boundary: 0 <= max_common <= min(len(tex1), len(text2))         


class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        m = len(text1)
        n = len(text2)
        dp = [[0 for _ in range(n + 1)] for _ in range(m + 1)]
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if text1[i - 1] == text2[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1] + 1
                else:
                    dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])
        return dp[m][n]

class Solution:
    def longestCommonSubsequence(self, A: str, B: str) -> int:
        if not A or not B:
            return 0
        
        m, n = len(A), len(B)
        f = [[None] * (n + 1) for _ in range(m + 1)]
        
        for i in range(m + 1):
            for j in range(n + 1):
                f[i][j] = 0
                if i == 0 or j == 0:
                    continue
                
                f[i][j] = max(f[i][j], f[i - 1][j], f[i][j - 1])
                
                if A[i - 1] == B[j - 1]:
                    f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1)
        
        return f[m][n]


class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        
        lengthone= len(text1)
        lengthtwo= len(text2)
        
        n = 1000
        ans = [[0]*n for _ in range(n)]
        
        for i in range(lengthone):
            for j in range(lengthtwo):
                if text1[i]==text2[j]:
                    ans[i][j]=ans[i-1][j-1]+1
                else:
                    ans[i][j]=max(ans[i-1][j],ans[i][j-1])
        
        return ans[lengthone-1][lengthtwo-1]

#         if ans[len(text1)][len(text2)] != 0:
#             return ans[len(text1)][len(text2)]

#         elif len(text1) == 0 or len(text2) == 0:
#             return 0

#         elif text1[-1] == text2[-1]:
#             ans[len(text1)][len(text2)] = LCS(text1[:-1], text2[:-1]) + 1
#             return ans[len(text1)][len(text2)]

#         else:
#             ans[len(text1)][len(text2)] = max(
#                 LCS(text1[:-1], text2), LCS(text1, text2[:-1]))
#             return ans[len(text1)][len(text2)]


#         text1 = \"This code is a sample text for longest common subsequence\"
#         text2 = \"abcde\"

#         LCS(text1, text2)

#         print(\"LCS of {} and {} = {}\".format(text1, text2, LCS(text1, text2)))



class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        if not text1: return 0
        
        l = len(text1)
        n = next((i for i, c in enumerate(text1) if c == text2[0]), l)
        commonSubstrings = [0] * n + [1] * (l - n)

        for c2 in text2[1:]:
            tmp = [0] * l
            tmp[0] = int(c2 == text1[0] or commonSubstrings[0])
            for i, c1 in enumerate(text1[1:], 1):
                if c1 == c2:
                    tmp[i] = commonSubstrings[i - 1] + 1
                else:
                    tmp[i] = max(tmp[i - 1], commonSubstrings[i])
            commonSubstrings = tmp

        return commonSubstrings[-1]


class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        #Top Down recursion - only works with LRU Cache
        @lru_cache(None)
        def helper(idx1, idx2):
            if len(text1) <= idx1 or len(text2) <= idx2:
                return 0
            if text1[idx1] == text2[idx2]:
                return 1 + helper(idx1+1, idx2+1)
            if text1[idx1] not in text2[idx2:]:
                return helper(idx1+1, idx2)
            else:
                newidx2 = idx2 + text2[idx2:].index(text1[idx1])
                return max(helper(idx1+1,newidx2+1) + 1, helper(idx1+1, idx2))
        return helper(0,0)
        
        


class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        dp = [ [0 for _ in range(len(text1) + 1)] for _ in range(len(text2) + 1) ];
        to_return = 0;
        for i in range(len(text2)):
            for j in range(len(text1)):
                r, c = i + 1, j + 1
                if(text1[j] == text2[i]):
                    dp[r][c] = 1 + dp[r-1][c-1]
                else:
                    dp[r][c] = max(dp[r-1][c], dp[r][c-1])
         
                to_return = max(to_return, dp[r][c]);
        return to_return;
        


class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
#            '' a. c. e 
#         ''  0 0. 0. 0.
#         a   0 1  0. 0
#         b   0 1  
#         c   0 1  
#         d   0
#         e   0
        
        if len(text1) == 0 or len(text2) == 0: return ''
        DP = [[0]*(len(text1)+1) for _ in range(len(text2)+1)]
        
        longest = 0
        for i in range(1,len(text2)+1):
            for j in range(1,len(text1)+1):
                if text2[i-1] == text1[j-1]:
                    DP[i][j] = max(max(DP[i-1][j-1]+1, DP[i-1][j]),DP[i][j-1])
                else:
                    DP[i][j] = max(DP[i-1][j],DP[i][j-1])
                longest = max(longest, DP[i][j])
                
        # print(DP)
        return longest

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        @lru_cache(None)
        def helper(idx1, idx2):
            if len(text1) <= idx1 or len(text2) <= idx2:
                return 0
            if text1[idx1] == text2[idx2]:
                return 1 + helper(idx1+1, idx2+1)
            if text1[idx1] not in text2[idx2:]:
                return helper(idx1+1, idx2)
            else:
                newidx2 = idx2 + text2[idx2:].index(text1[idx1])
                return max(helper(idx1+1,newidx2+1) + 1, helper(idx1+1, idx2))
        return helper(0,0)
        
        


class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        D = []
        for i in range(len(text1) + 1):
            D.append([0] * (len(text2) + 1))
        
        for i in range(1, len(text1) + 1):
            for j in range(1, len(text2) + 1):
                delta = 1 if text1[i-1] == text2[j-1] else 0
                D[i][j] = max(D[i-1][j], D[i][j-1], D[i-1][j-1] + delta)
        
        return D[len(text1)][len(text2)]


class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        if len(text2) > len(text1):
            text1,text2=text2,text1
        pre = [0] * (len(text1)+1)
        cur = [0] * (len(text2)+1)
        
        for col in reversed(list(range(len(text1)))):
            for row in reversed(list(range(len(text2)))):
                if (text1[col] == text2[row]):
                    cur[row] = 1 + pre[row+1]
                else:
                    cur[row] = max(pre[row],cur[row + 1])
            pre, cur = cur, pre
        return pre[0]
                    
            
            
        


class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        if len(text2) > len(text1):
            text1, text2 = text2, text1
        dp = [[0] * (len(text1)+1) for _ in range(len(text2)+1)]
        for i in range(1, len(text2)+1):
            for j in range(1, len(text1)+1):
                max_sides = max(dp[i-1][j], dp[i][j-1])
                if text1[j-1] == text2[i-1]:
                    dp[i][j] = max(dp[i-1][j-1] + 1, max_sides)
                else:
                    dp[i][j] = max(dp[i-1][j-1], max_sides)
        return dp[-1][-1]

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        text1 = list(text1)
        text2 = list(text2)
        n = len(text1)
        m = len(text2)
        dp = [[0 for i in range(m+1)] for i in range(n+1)]
        for i in range(1,n+1):
            for j in range(1,m+1):
                if text1[i-1] == text2[j-1]:
                    dp[i][j] = 1+dp[i-1][j-1]
                else:
                    dp[i][j] = max(dp[i-1][j],dp[i][j-1])
        return dp[n][m]
        
    
        


class Solution:
    def longestCommonSubsequence(self, s1: str, s2: str) -> int:
        if s1 == '' or s2 == '':
            return 0
        dp = [[0 for y in s2] for x in s1]
        for i in range(0, len(s1)):
            for j in range(0, len(s2)):
                if i == 0 and j == 0:
                    dp[i][j] = 1 if s1[i] == s2[j] else 0
                elif i == 0:
                    dp[i][j] = 1 if s1[i] == s2[j] else dp[i][j - 1]
                elif j == 0:
                    dp[i][j] = 1 if s1[i] == s2[j] else dp[i - 1][j]
                else:
                    dp[i][j] = max([dp[i - 1][j - 1] + 1 if s1[i] == s2[j] else 0, dp[i - 1][j], dp[i][j - 1]])
        
        return dp[-1][-1]
        
        
        
        
        


import numpy as np
class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) :
        dp = np.full((len(text1)+1,len(text2)+1),0)
        print((dp.shape))
        for i in range(dp.shape[0]-2,-1,-1) :
            for j in range(dp.shape[1]-2,-1,-1) :
                if(text1[i]==text2[j]) :
                    dp[i,j] = 1 + dp[i+1][j+1]
                    
                else :
                    dp[i,j] = max(dp[i+1,j],dp[i,j+1])
                    
        return dp[0,0]
            
        


class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        len_1, len_2 = len(text1), len(text2)
        # Append an additional 0 to stand for the case of \"\" for both strings
        dp = [[0] * (len_2 + 1) for _ in range(len_1 + 1)]
        max_len_subseq = 0
        
        for j in range(1, len_2 + 1):
            for i in range(1, len_1 + 1):
                if text1[i-1] == text2[j-1]:
                    dp[i][j] = dp[i-1][j-1] + 1
                else:
                    dp[i][j] = max(dp[i][j-1], dp[i-1][j])  
                max_len_subseq = max(max_len_subseq, dp[i][j])
        return max_len_subseq