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:\n    def longestCommonSubsequence(self, a: str, b: str) -> int:\n        last, current = [0] * (len(b) + 1), [0] * (len(b) + 1)\n        \n        for i in range(len(a) - 1, -1, -1):\n            for j in range(len(b) - 1, -1, -1):\n                if a[i] == b[j]:\n                    current[j] = 1 + last[j + 1]\n                else:\n                    current[j] = max(last[j], current[j + 1])\n            last = current\n            current = [0] * (len(b) + 1)\n        return last[0]", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        n, m = len(text1), len(text2)\n        \n        if n == 0 or m == 0:\n            return max(n, m)\n        \n        DeleteT1 = 0\n        DeleteT2 = 1\n        Match = 2\n        \n        dp = [[(0, None) for j in range(m+1)] for i in range(n+1)]  ###(value, direction)\n        \n        for i in range(1,n+1):\n            dp[i][0] = (i,DeleteT1)\n        for j in range(1,m+1):\n            dp[0][j] = (j,DeleteT2)\n            \n        for i in range(1, n+1):\n            for j in range(1, m+1):\n                if text1[i-1] == text2[j-1]:\n                    dp[i][j] = (dp[i-1][j-1][0],Match)\n                    continue\n                \n                val = min(dp[i-1][j][0], dp[i][j-1][0])\n                if val == dp[i-1][j][0]:  ###not dp[i-1][j]\n                    dp[i][j] = (val+1,DeleteT1)\n                else:\n                    dp[i][j] = (val+1,DeleteT2)\n        \n        #print(len(dp), len(dp[0]))\n        #print(dp)\n        i,j = n,m\n        T1Length = n\n        while i >= 0 and j >= 0:\n            comb = dp[i][j]\n            if comb[1] == DeleteT1:\n                i -= 1\n                T1Length -= 1\n            elif comb[1] == DeleteT2:\n                j -= 1\n            else:\n                i -= 1\n                j -= 1\n        \n        #print(dp)\n        return T1Length", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        \n        s1,s2=text1,text2\n        len_s1,len_s2=len(s1),len(s2)\n        pick_s1_or_s2,pick_s1,pick_s2=0,1,2\n        \n        \n        match_table=[[0 for i in range(len_s2)] for j in range(len_s1)]\n        \n        for i in range(len_s1):\n            for j in range(len_s2):\n                \n                if(s1[i]==s2[j]):\n                    \n                    if(i==0 or j==0):\n                        match_table[i][j]=1\n                    \n                    else:\n                        match_table[i][j]=1+match_table[i-1][j-1]\n                else:\n                    if(i==0 and j>0):\n                        match_table[i][j]=match_table[i][j-1]\n                    elif(j==0 and i>0):\n                        match_table[i][j]=match_table[i-1][j]\n                    elif(i>0 and j>0):\n                        if(match_table[i-1][j]>match_table[i][j-1]):\n                            match_table[i][j]=match_table[i-1][j]\n                        else:\n                            match_table[i][j]=match_table[i][j-1]\n        return match_table[len_s1-1][len_s2-1]\n                        \n        \n        \n                                      \n        \n", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        dp = [[0 for i in range(len(text1)+1)] for j in range(len(text2)+1)]\n        for i in range(1,len(dp)):\n            for j in range(1,len(dp[0])): # in case of letter out of boarder \n                dp[i][j] = max(dp[i-1][j],dp[i][j-1])\n                if text2[i-1] == text1[j-1]: # one more letter to sub sequence\n                    dp[i][j] = dp[i-1][j-1] + 1 \n        return dp[-1][-1]", "class Solution:\n    def recursiveLCS(self, t1, t2):\n        if not t1 or not t2:\n            return 0\n        else:\n            if t1[0] == t2[0]:\n                return 1 + self.recursiveLCS(t1[1:], t2[1:])\n            else:\n                left = self.recursiveLCS(t1[1:], t2)\n                right = self.recursiveLCS(t1, t2[1:])\n                return max(left, right)\n        \n    def recursiveLongestCommonSubsequence(self, text1: str, text2: str) -> int:\n        return self.recursiveLCS(text1, text2)\n    \n\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        # maybe do checks here but can probably get passed it\n        DP = [[0]*(len(text2)+1) for i in range(len(text1)+1)]\n        # MAYBE DO BASE CASES TO PRACTICE\n        for i in range(1, len(text1)+1):\n            for j in range(1, len(text2)+1):\n                if text1[i-1] == text2[j-1]:\n                    DP[i][j] = 1 + DP[i-1][j-1]\n                else:\n                    left = DP[i-1][j]\n                    right = DP[i][j-1]\n                    DP[i][j] = max(left, right)\n        for row in DP:\n            print(row)\n        return DP[len(text1)][len(text2)]\n        \n        \n", "from collections import defaultdict\nclass Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        dp = defaultdict(int)\n        \n        for i in range(len(text1)):\n            for j in range(len(text2)):\n                if text1[i] == text2[j]:\n                    dp[(i, j)] = 1 + dp[(i-1, j-1)]\n                else:\n                    dp[(i, j)] = max(dp[(i-1, j)], dp[(i, j-1)])\n                    \n        return dp[(len(text1)-1, len(text2)-1)]", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        str1, str2 = text1, text2\n\n        num_rows = len(str1) + 1\n        num_cols = len(str2) + 1\n        lengths = [[0 for _ in range(num_cols)] for _ in range(num_rows)]\n        for row in range(1, num_rows):\n            for col in range(1, num_cols):\n                if str1[row - 1] == str2[col - 1]:\n                    lengths[row][col] = lengths[row - 1][col - 1] + 1\n                else:\n                    lengths[row][col] = max(lengths[row - 1][col], lengths[row][col - 1])\n\n        return lengths[-1][-1]\n", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        m, n = len(text1), len(text2)\n        dp = [[0] * (n + 1) for i in range(m + 1)]\n        \n        for i in range(m + 1):\n            for j in range(n + 1):\n                if i != 0 and j != 0:\n                    if text1[i - 1] == text2[j - 1]:\n                        dp[i][j] = dp[i - 1][j - 1] + 1\n                    dp[i][j] = max(dp[i][j], max(dp[i - 1][j], dp[i][j - 1]))\n        return dp[-1][-1]\n", "import numpy as np\n#from functools import lru_cache\nclass Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        if len(text1) == 0 or len(text2) == 0:\n            return 0\n        \n        m = len(text1)\n        n = len(text2)\n        #return self.dp(text1, text2, m-1, n-1)\n        \n        A = np.zeros((m+1, n+1),int)\n        \n        for i in range(1,m+1):\n            for j in range(1,n+1):\n                if text1[i-1] == text2[j-1]:\n                    A[i,j] = A[i-1,j-1] +1\n                else:\n                    A[i,j] = max(A[i-1,j], A[i,j-1])\n        return A[-1,-1]\n        \n    # @lru_cache(maxsize=None)\n    # def dp(self, text1, text2, i, j):\n    #     if i  < 0 or j < 0:\n    #         return 0\n    #     if text1[i] == text2[j]:\n    #         return self.dp(text1, text2, i-1, j-1) + 1\n    #     else:\n    #         return max(self.dp(text1, text2, i-1, j), self.dp(text1, text2, i, j-1))\n", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        dp = [[0]*(len(text2)+1) for i in range(len(text1)+1)]\n        \n        dp[0][0] = 0\n        \n        for i in range(1, len(dp)):\n            for j in range(1, len(dp[0])):\n                if text1[i-1] == text2[j-1]:\n                    dp[i][j] = dp[i-1][j-1] + 1\n                else:\n                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])\n        \n        return dp[len(text1)][len(text2)]\n            \n    \n    \n    \n    # $ a c e\n    # a\n    # b\n    # c\n    # d\n    # e\n", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        m=len(text1)\n        n=len(text2)\n        t=[[0 for i in range(n+1)] for j in range(m+1)]\n        for i in range(1,m+1):\n            for j in range(1,n+1):\n                if text1[i-1]==text2[j-1]:\n                    t[i][j]=1+t[i-1][j-1]\n                else:\n                    t[i][j]=max(t[i][j-1],t[i-1][j])\n        return t[-1][-1]\n", "class Solution:\n    # approach 3\n    def longestCommonSubsequence(self, s1: str, s2: str) -> int:\n        def print_grid(grid):\n            for row in grid:\n                print(row)\n        \n        dp_row = [0] * (len(s2) + 1)\n        dp_row_pre = [0] * (len(s2) + 1)\n        N, M = len(s1), len(s2)\n        for i in range(N - 1, -1, -1):\n            for j in range(M - 1, -1, -1):\n                if s1[i] == s2[j]:\n                    dp_row[j] = dp_row_pre[j + 1] + 1\n                else:\n                    dp_row[j] = max(dp_row_pre[j], dp_row[j + 1])\n            dp_row_pre, dp_row = dp_row, dp_row_pre\n                # print(\\\"update row=\\\", i, \\\", col=\\\", j)\n                # print_grid(dp_grid)\n        return dp_row_pre[0]\n        \n    # approach 1: recursive memorization\n#     def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        \n#         @lru_cache(maxsize=None)\n#         def memo_solve(p1, p2):\n#             if p1 == len(text1) or p2 == len(text2):\n#                 return 0\n            \n#             # option 1: we don't include text1[p1] in the solution\n#             option_1 = memo_solve(p1 + 1, p2)\n            \n#             # option 2: we include p1 in the solution, as long as there is a match in p2\n#             first_occurrence = text2.find(text1[p1], p2)\n#             option_2 = 0\n#             if first_occurrence != -1:\n#                 option_2 = 1 + memo_solve(p1 + 1, first_occurrence + 1)\n            \n#             return max(option_1, option_2)\n        \n#         return memo_solve(0, 0)\n    \n      # approach 2\n#     def longestCommonSubsequence(self, s1: str, s2: str) -> int:\n        \n#         @lru_cache(maxsize=None)\n#         def mem_solve(p1: int, p2: int) -> int:\n#             # base case \n#             if p1 == len(s1) or p2 == len(s2):\n#                 return 0\n            \n#             # option 1 match the first letter\n#             if s1[p1] == s2[p2]:\n#                 return 1 + mem_solve(p1 + 1, p2 + 1)\n            \n#             # option 2\n#             return max(mem_solve(p1, p2 + 1), mem_solve(p1 + 1, p2))\n        \n#         return mem_solve(0, 0)\n        \n", "from functools import lru_cache\nclass Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        \n        \n        l1 = len(text1)\n        l2 = len(text2)\n        \n        memo = [[0 for _ in range(max(l1,l2)+1)] for _ in range(max(l1,l2)+1)]\n        \n        \n        current=0\n        \n        for i in range(1,l1+1):\n            for j in range(1,l2+1):\n                \n                current = memo[i-1][j-1]\n                \n                if text1[i-1]==text2[j-1]:\n                    memo[i][j]=1+memo[i-1][j-1]\n                else:\n                    memo[i][j]=max(memo[i-1][j],memo[i][j-1])\n                \n                current=max(memo[i][j],current)\n \n        \n        return current\n                \n            \n            \n", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        \n        m = len(text1)\n        n = len(text2)\n        \n        dp = [[0 for i in range(n+1)] for j in range(m+1)]\n        \n        for i in range(1,m+1):\n            for j in range(1,n+1):\n                if text1[i-1]==text2[j-1]:\n                    dp[i][j] = dp[i-1][j-1]+1\n                else:\n                    dp[i][j] = max(dp[i-1][j],dp[i][j-1])\n                    \n        return dp[m][n]\n        \n", "import numpy as np\nclass Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        if len(text1) == 0 or len(text2) == 0:\n            return 0\n        \n        m = len(text1)\n        n = len(text2)\n        \n        A = np.zeros((m+1, n+1),int)\n        \n        for i in range(1,m+1):\n            for j in range(1,n+1):\n                if text1[i-1] == text2[j-1]:\n                    A[i,j] = A[i-1,j-1] +1\n                else:\n                    A[i,j] = max(A[i-1,j], A[i,j-1])\n        return A[-1,-1]\n", "class Solution:\n    # def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n    #     matrix = [[None]*(len(text2)+1) for i in range(len(text1)+1)]\n    #     for j in range(len(text2)+1):\n    #         matrix[0][j] = 0\n    #     for i in range(len(text1)+1):\n    #         matrix[i][0] = 0\n    #     for i in range(1, len(text1)+1):\n    #         for j in range(1, len(text2)+1):\n    #             if text1[i-1] == text2[j-1]:\n    #                 matrix[i][j] = 1 + matrix[i-1][j-1]\n    #             else:\n    #                 matrix[i][j] = max(matrix[i-1][j], matrix[i][j-1])\n    #     return matrix[len(text1)][len(text2)]\n    \n    \n    \n    \n    \n    \n\n    \n    \n    \n\n\n    def longestCommonSubsequence(self, s1, s2):\n        def _longest_common_subsequence(i, j, cache):\n            if i < 0 or j < 0:\n                return 0\n            elif cache[i][j] != None:\n                return cache[i][j]\n            elif s1[i] == s2[j]:\n                answer = 1 + _longest_common_subsequence(i-1, j-1, cache)\n                cache[i][j] = answer\n                return answer\n            else:\n                answer = max(_longest_common_subsequence(i, j-1, cache), _longest_common_subsequence(i-1, j, cache))\n                cache[i][j] = answer\n                return answer\n        return _longest_common_subsequence(len(s1)-1, len(s2)-1, [[None]*len(s2) for i in range(len(s1))])", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        l1, l2 = len(text1), len(text2)\n        dp = [[0]*l2 for i in range(l1)]\n        \n        get = lambda r, c: 0 if -1 in [r, c] else dp[r][c]\n        \n        for r, c1 in enumerate(text1): # pos, char\n            for c, c2 in enumerate(text2):              \n                \n                if c1 == c2:\n                    dp[r][c] = get(r-1, c-1) + 1\n                else:\n                    dp[r][c] = max(get(r-1, c), get(r, c-1))\n               \n        for i in dp:\n            print(i)\n        return dp[-1][-1]\n                        \n", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        \n        n = len(text1)\n        m = len(text2)\n        \n        dp = []\n        \n        for i in range(n):\n            dp.append([-1]*m)\n        \n        def lcs(i,j):\n            \n            if(i>=n or j>=m):\n                return 0\n            \n            if(dp[i][j]!=-1):\n                return dp[i][j]\n            \n            if(text1[i]==text2[j]):\n                ans = 1 + lcs(i+1,j+1)\n            else:\n                ans = max(lcs(i+1,j),lcs(i,j+1))\n            \n            dp[i][j] = ans\n            \n            return ans\n        return lcs(0,0)\n", "class Solution:\n    def longestCommonSubsequence(self, text1, text2):\n\n\n        def compute(x, y):\n            if x == len(text1):\n                return 0\n            if y == len(text2):\n                return 0\n\n            if text1[x] == text2[y]:\n                return 1 + compute(x+1, y+1)\n\n            return max([compute(x+1, y), compute(x, y+1)])\n\n        cache = {}\n\n        for x in range(-1, len(text1)+1):\n            cache[(x, -1)] = 0\n\n        for y in range(-1, len(text2)+1):\n            cache[(-1, y)] = 0\n\n        for x in range(len(text1)):\n            for y in range(len(text2)):\n                if text1[x] == text2[y]:\n                    cache[(x, y)] = 1 + cache[(x-1, y-1)]\n                else:\n                    cache[(x, y)] = max([cache[(x, y-1)], cache[(x-1, y)]])\n\n        return cache[(len(text1)-1, len(text2)-1)]\n", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        if len(text1) == 0 or len(text2) == 0:\n            return 0\n        \n#         grid = [[[None, 0, None, None] for i in range(len(text1) + 1)] for i in range(len(text2) + 1)] \n        \n#         for i in range(1, len(text2) + 1):\n#             for j in range(1, len(text1) + 1):\n#                 if text1[j - 1] == text2[i - 1]:\n#                     grid[i][j] = [text2[i - 1], grid[i - 1][j - 1][1] + 1, i - 1, j - 1]\n#                 else:\n#                     if grid[i - 1][j][1] > grid[i][j - 1][1]:\n#                         grid[i][j] = [None, grid[i - 1][j][1], i - 1, j]\n#                     else:\n#                         grid[i][j] = [None, grid[i][j - 1][1], i, j - 1]\n#         return grid[-1][-1][1]\n    \n    \n        grid = [[[0] for i in range(len(text1) + 1)] for i in range(len(text2) + 1)] \n        \n        for i in range(1, len(text2) + 1):\n            for j in range(1, len(text1) + 1):\n                if text1[j - 1] == text2[i - 1]:\n                    grid[i][j] = [grid[i - 1][j - 1][0] + 1]\n                else:\n                    if grid[i - 1][j] > grid[i][j - 1]:\n                        grid[i][j] = grid[i - 1][j]\n                    else:\n                        grid[i][j] = grid[i][j - 1]\n        return grid[-1][-1][0]\n", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        memo = [[-1] * (len(text2)+1) for _ in range(len(text1)+1)]\n        return self.helper(text1, text2, 0, 0, memo)\n    def helper(self, s1, s2, i, j, memo):\n        if memo[i][j] != -1:\n            return memo[i][j]\n        if i == len(s1) or j == len(s2):\n            return 0\n        ans = 0\n        if s1[i] == s2[j]:\n            ans = 1 + self.helper(s1, s2, i+1, j+1, memo)\n        else:\n            ans = max(self.helper(s1, s2, i+1, j, memo), self.helper(s1, s2, i, j+1, memo))\n        memo[i][j] = ans\n        return ans\n        \n#     def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n#         m, n = len(text1), len(text2)\n#         dp = [[0] * (n+1) for _ in range(m+1)]\n#         for i in range(1, m+1):\n#             for j in range(1, n+1):\n#                 if text1[i-1] == text2[j-1]:\n#                     dp[i][j] = 1 + dp[i-1][j-1]\n#                 else:\n#                     dp[i][j] = max(dp[i-1][j], dp[i][j-1])\n                \n#         return dp[-1][-1]\n", "from functools import lru_cache\nclass Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        \n        \n        @lru_cache(None)\n        def lcs(idxA, idxB):\n            if idxA < 0 or idxB < 0:\n                return 0\n\n            if text1[idxA] == text2[idxB]:\n                return 1 + lcs(idxA - 1, idxB - 1)\n\n            return max(lcs(idxA - 1, idxB), lcs(idxA, idxB - 1))\n\n        return lcs(len(text1) - 1, len(text2) - 1)\n            \n            \n", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        # If text1 doesn't reference the shortest string, swap them.\n        if len(text2) < len(text1):\n            text1, text2 = text2, text1\n        \n        \n        # The previous column starts with all 0's and like before is 1\n        # more than the length of the first word.\n        previous = [0] * (len(text1) + 1)\n        # Create a new array to represent the current column.\n        current = [0] * (len(text1) + 1)\n        \n        # Iterate up each column, starting from the last one.\n        for col in reversed(range(len(text2))):\n            for row in reversed(range(len(text1))):\n                if text2[col] == text1[row]:\n                    current[row] = 1 + previous[row + 1]\n                else:\n                    current[row] = max(previous[row], current[row + 1])\n            # The current column becomes the previous one.\n            previous, current = current, previous\n        \n        # The original problem's answer is in previous[0]. Return it.\n        return previous[0]\n        \n        '''\n        # Make a grid of 0's with len(text2) + 1 columns \n        # and len(text1) + 1 rows.\n        dp_grid = [[0] * (len(text2) + 1) for _ in range(len(text1) + 1)]\n        \n        # Iterate up each column, starting from the last one.\n        for col in reversed(range(len(text2))):\n            for row in reversed(range(len(text1))):\n                # If the corresponding characters for this cell are the same...\n                if text2[col] == text1[row]:\n                    dp_grid[row][col] = 1 + dp_grid[row + 1][col + 1]\n                # Otherwise they must be different...\n                else:\n                    dp_grid[row][col] = max(dp_grid[row + 1][col], dp_grid[row][col + 1])\n        \n        # The original problem's answer is in dp_grid[0][0]. Return it.\n        return dp_grid[0][0]\n        '''\n        \n        '''\n        from functools import lru_cache\n        @lru_cache(maxsize=None)\n        def memo_solve(p1, p2):\n            \n            # Base case: If either string is now empty, we can't match\n            # up anymore characters.\n            if p1 == len(text1) or p2 == len(text2):\n                return 0\n            \n            # Recursive case 1.\n            if text1[p1] == text2[p2]:\n                return 1 + memo_solve(p1 + 1, p2 + 1)\n            \n            # Recursive case 2.\n            else:\n                return max(memo_solve(p1, p2 + 1), memo_solve(p1 + 1, p2))\n            \n        return memo_solve(0, 0)\n        '''\n        \n        \n        '''\n        def memo_solve(p1, p2):\n            \n            # Base case: If either string is now empty, we can't match\n            # up anymore characters.\n            if p1 == len(text1) or p2 == len(text2):\n                return 0\n            \n            # Option 1: We don't include text1[p1] in the solution.\n            option_1 = memo_solve(p1 + 1, p2)\n            \n            # Option 2: We include text1[p1] in the solution, as long as\n            # a match for it in text2 at or after p2 exists.\n            first_occurence = text2.find(text1[p1], p2)\n            option_2 = 0\n            if first_occurence != -1:\n                option_2 = 1 + memo_solve(p1 + 1, first_occurence + 1)\n            \n            # Return the best option.\n            return max(option_1, option_2)\n                \n        return memo_solve(0, 0)'''", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        rows = len(text1)\n        cols = len(text2)\n        \n        dp = [[0 for j in range(cols)] for i in range(rows)]\n        if text1[rows-1] == text2[cols-1]:\n            dp[rows-1][cols-1] = 1\n        for i in range(rows-1, -1, -1):\n            for j in range(cols-1, -1, -1):\n                if i == rows - 1 and j == cols-1:\n                    continue\n                right = 0\n                down = 0\n                rightdown = 0\n                if i < rows - 1:\n                    down = dp[i+1][j]\n                if j < cols - 1:\n                    right = dp[i][j+1]\n                if i < rows - 1 and j < cols - 1:\n                    rightdown = dp[i+1][j+1]\n                if text1[i] == text2[j]:\n                    dp[i][j] = 1 + rightdown\n                else:\n                    dp[i][j] = max(down, right)\n        return dp[0][0]", "class Solution:\n    def longestCommonSubsequence(self, a: str, b: str) -> int:\n        n1, n2 = len(a), len(b)\n        memo = [[None] * (n2+1) for i in range(n1+1)]\n        def helper(i, j):\n            if memo[i][j] == None:\n                if i == n1 or j == n2:\n                    memo[i][j] = 0\n\n                elif a[i] == b[j]:\n                    return 1 + helper(i+1, j+1)\n                else:\n                    memo[i][j] = max(helper(i, j+1), helper(i+1, j))\n            return memo[i][j]\n\n        return helper(0, 0)", "from collections import defaultdict\nclass Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        # dp = defaultdict(lambda: -1)\n        \n        @lru_cache(maxsize = None)\n        def helper(n, m):\n            if m < 0 or n < 0:\n                return 0\n            # if dp[(m, n)] == -1:\n            if text1[n] == text2[m]:\n                length = 1 + helper(n-1, m-1)\n            else:\n                length = max(helper(n-1, m), \n                            helper(n, m-1))\n                # dp[(m, n)] = length\n            return length\n        return helper(len(text1)-1, len(text2)-1)", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        import functools\n        @functools.lru_cache(None)\n        def helper(i,j):\n            if i<0 or j<0:\n                return 0\n            if text1[i]==text2[j]:\n                return helper(i-1,j-1)+1\n            return max(helper(i-1,j),helper(i,j-1))\n        return helper(len(text1)-1,len(text2)-1)\n            \n", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        m, n = len(text1), len(text2)\n        \n        @lru_cache(None)\n        def find(i, j):\n            if i >= m or j >= n:\n                return 0\n            if text1[i] == text2[j]:\n                return 1+find(i+1, j+1)\n            else:\n                return max(find(i+1, j), find(i, j+1))\n        \n        return find(0, 0)\n            \n", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        rows = len(text1)\n        cols = len(text2)\n        \n        dp = [[0 for j in range(cols)] for i in range(rows)]\n        if text1[rows-1] == text2[cols-1]:\n            dp[rows-1][cols-1] = 1\n        for i in range(rows-1, -1, -1):\n            for j in range(cols-1, -1, -1):\n                if i == rows - 1 and j == cols-1:\n                    continue\n                print1 = False\n                # if i == 2:\n                #     print1 = True\n                if print1:\n                    print(i, j)\n                right = 0\n                down = 0\n                rightdown = 0\n                if i < rows - 1:\n                    down = dp[i+1][j]\n                if j < cols - 1:\n                    right = dp[i][j+1]\n                if i < rows - 1 and j < cols - 1:\n                    rightdown = dp[i+1][j+1]\n                # print(text1[i])\n                # print(text2[j])\n                # print(down)\n                # print(right)\n                if text1[i] == text2[j]:\n                    dp[i][j] = 1 + rightdown\n                else:\n                    dp[i][j] = max(down, right)\n        print(dp)\n        return dp[0][0]", "from functools import lru_cache\nclass Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        \n        @lru_cache(maxsize =None)\n        def memo(l1,l2):\n            if l1 == len(text1) or l2 == len(text2):\n                return 0\n            if text1[l1]==text2[l2]:\n                return 1+ memo(l1+1,l2+1)\n            else:\n                return max(memo(l1+1,l2),memo(l1,l2+1))\n        return memo(0,0)", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        \n        @lru_cache(None)\n        def recur(i, j):\n            if i == -1 or j == -1:\n                return 0\n            \n            if text1[i] == text2[j]:\n                return recur(i-1, j-1) + 1\n            else:\n                return max(recur(i-1,j), recur(i, j -1))\n            \n        return recur(len(text1) - 1, len(text2) - 1)", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        # If text1 doesn't reference the shortest string, swap them.\n        if len(text2) < len(text1):\n            text1, text2 = text2, text1\n        \n        \n        # The previous column starts with all 0's and like before is 1\n        # more than the length of the first word.\n        previous = [0] * (len(text1) + 1)\n        \n        # Iterate up each column, starting from the last one.\n        for col in reversed(range(len(text2))):\n            # Create a new array to represent the current column.\n            current = [0] * (len(text1) + 1)\n            for row in reversed(range(len(text1))):\n                if text2[col] == text1[row]:\n                    current[row] = 1 + previous[row + 1]\n                else:\n                    current[row] = max(previous[row], current[row + 1])\n            # The current column becomes the previous one.\n            previous = current\n        \n        # The original problem's answer is in previous[0]. Return it.\n        return previous[0]\n        \n        '''\n        # Make a grid of 0's with len(text2) + 1 columns \n        # and len(text1) + 1 rows.\n        dp_grid = [[0] * (len(text2) + 1) for _ in range(len(text1) + 1)]\n        \n        # Iterate up each column, starting from the last one.\n        for col in reversed(range(len(text2))):\n            for row in reversed(range(len(text1))):\n                # If the corresponding characters for this cell are the same...\n                if text2[col] == text1[row]:\n                    dp_grid[row][col] = 1 + dp_grid[row + 1][col + 1]\n                # Otherwise they must be different...\n                else:\n                    dp_grid[row][col] = max(dp_grid[row + 1][col], dp_grid[row][col + 1])\n        \n        # The original problem's answer is in dp_grid[0][0]. Return it.\n        return dp_grid[0][0]\n        '''\n        \n        '''\n        from functools import lru_cache\n        @lru_cache(maxsize=None)\n        def memo_solve(p1, p2):\n            \n            # Base case: If either string is now empty, we can't match\n            # up anymore characters.\n            if p1 == len(text1) or p2 == len(text2):\n                return 0\n            \n            # Recursive case 1.\n            if text1[p1] == text2[p2]:\n                return 1 + memo_solve(p1 + 1, p2 + 1)\n            \n            # Recursive case 2.\n            else:\n                return max(memo_solve(p1, p2 + 1), memo_solve(p1 + 1, p2))\n            \n        return memo_solve(0, 0)\n        '''\n        \n        \n        '''\n        def memo_solve(p1, p2):\n            \n            # Base case: If either string is now empty, we can't match\n            # up anymore characters.\n            if p1 == len(text1) or p2 == len(text2):\n                return 0\n            \n            # Option 1: We don't include text1[p1] in the solution.\n            option_1 = memo_solve(p1 + 1, p2)\n            \n            # Option 2: We include text1[p1] in the solution, as long as\n            # a match for it in text2 at or after p2 exists.\n            first_occurence = text2.find(text1[p1], p2)\n            option_2 = 0\n            if first_occurence != -1:\n                option_2 = 1 + memo_solve(p1 + 1, first_occurence + 1)\n            \n            # Return the best option.\n            return max(option_1, option_2)\n                \n        return memo_solve(0, 0)'''", "from functools import lru_cache as memoize\n\nclass Solution():\n    def longestCommonSubsequence(self, s1, s2):\n        @memoize(None)\n        def lcs(m,n):\n            \n            if(m==0 or n==0):\n                return 0\n            \n            if s1[m-1] == s2[n-1]:\n                return 1 + lcs(m-1,n-1)\n            \n            else:\n                \n                return max(lcs(m-1,n),lcs(m,n-1))\n            \n            \n        return lcs(len(s1),len(s2))", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        from functools import lru_cache\n        @lru_cache(maxsize=None)\n        def memo_solve(p1, p2):\n            \n            # Base case: If either string is now empty, we can't match\n            # up anymore characters.\n            if p1 == len(text1) or p2 == len(text2):\n                return 0\n            \n            # Recursive case 1.\n            if text1[p1] == text2[p2]:\n                return 1 + memo_solve(p1 + 1, p2 + 1)\n            \n            # Recursive case 2.\n            else:\n                return max(memo_solve(p1, p2 + 1), memo_solve(p1 + 1, p2))\n            \n        return memo_solve(0, 0)\n        \n        \n        \n        '''\n        def memo_solve(p1, p2):\n            \n            # Base case: If either string is now empty, we can't match\n            # up anymore characters.\n            if p1 == len(text1) or p2 == len(text2):\n                return 0\n            \n            # Option 1: We don't include text1[p1] in the solution.\n            option_1 = memo_solve(p1 + 1, p2)\n            \n            # Option 2: We include text1[p1] in the solution, as long as\n            # a match for it in text2 at or after p2 exists.\n            first_occurence = text2.find(text1[p1], p2)\n            option_2 = 0\n            if first_occurence != -1:\n                option_2 = 1 + memo_solve(p1 + 1, first_occurence + 1)\n            \n            # Return the best option.\n            return max(option_1, option_2)\n                \n        return memo_solve(0, 0)'''", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        \n        \n        def lcs(text1,text2,m,n,dp):\n            \n            \n            if m==0 or n==0:\n                return 0\n            \n            if dp[m][n] !=-1:\n                return dp[m][n]\n            \n            if text1[m-1] == text2[n-1]:\n                dp[m][n] = 1 + lcs(text1,text2,m-1,n-1,dp)\n                return dp[m][n]\n            \n            \n            \n            else:\n                dp[m][n] = max(lcs(text1,text2,m,n-1,dp),lcs(text1,text2,m-1,n,dp))\n                return dp[m][n]\n            \n         \n        \n        m = len(text1)\n        \n        n = len(text2)\n        \n        dp = [[-1 for i in range(n+1)] for j in range(m+1)]   \n\n        res = lcs(text1,text2,m,n,dp)\n  \n    \n        return res\n", "from functools import lru_cache\n\nclass Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        \n        @lru_cache(maxsize=None)\n        def memo_solve(p1, p2):\n            \n            # Base case: If either string is now empty, we can't match\n            # up anymore characters.\n            if p1 == len(text1) or p2 == len(text2):\n                return 0\n            \n            # Recursive case 1.\n            if text1[p1] == text2[p2]:\n                return 1 + memo_solve(p1 + 1, p2 + 1)\n            \n            # Recursive case 2.\n            else:\n                return max(memo_solve(p1, p2 + 1), memo_solve(p1 + 1, p2))\n            \n        return memo_solve(0, 0)", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        \n        @lru_cache(maxsize = None)\n        def memo_solve(index1, index2):\n            \n            if index1 == len(text1) or index2 == len(text2):\n                return 0\n            \n            if text1[index1] == text2[index2]:\n                return 1 + memo_solve(index1 + 1, index2 + 1)\n            else:\n                return max(memo_solve(index1, index2+1), memo_solve(index1+1, index2))\n            \n        return memo_solve(0,0)", "from functools import lru_cache\n\nclass Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        \n        @lru_cache(maxsize=None)\n        def memo(i, j):\n            if i == len(text1) or j == len(text2):\n                return 0\n            \n            if text1[i] == text2[j]:\n                return 1 + max(memo(i + 1, j + 1), memo(i + 1, j + 1))\n            else:\n                return max(memo(i + 1, j), memo(i, j + 1))\n        \n        return memo(0, 0)\n", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        \n        \n        @lru_cache(maxsize=None)\n        def helper(i, j):\n            \n            if i >= len(text1) or j >= len(text2):\n                return 0\n            \n            elif text1[i] == text2[j]:\n                return 1 + helper(i+1, j+1)\n            \n            l = helper(i + 1, j)\n            r = helper(i, j + 1)\n            \n            return max(l, r)\n                \n        return helper(0, 0)\n                \n                \n", "from functools import lru_cache\n\nclass Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        \n        @lru_cache(maxsize=None)\n        def memo_solve(p1, p2):\n            \n            # Base case: If either string is now empty, we can't match\n            # up anymore characters.\n            if p1 == len(text1) or p2 == len(text2):\n                return 0\n            \n            if text1[p1] == text2[p2]:\n                return 1 + memo_solve(p1+1, p2+1)\n            else:\n                return max(memo_solve(p1+1, p2),\n                           memo_solve(p1, p2+1))\n                \n        return memo_solve(0, 0)", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        \n        prev = [0] * (len(text2) + 1)\n        curr = [0] * (len(text2) + 1)\n        \n        for row in range(len(text1)):\n            for col in range(len(text2)):\n                if text1[row] == text2[col]:\n                    curr[col + 1] = 1 + prev[col]\n                else:\n                    curr[col + 1] = max(prev[col + 1], curr[col])\n                    \n            prev, curr = curr, prev\n                    \n        return prev[-1]", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n#         dp = [[0] * (len(text1) + 1) for _ in range(len(text2) + 1)]\n        \n#         # logic: if same, add 1, else max(try each without first)\n#         # if row,col V == same, == prev diag + 1\n#         # else: = max(row-1,col, row,col-1)\n        \n#         for row in range(1, len(text2) + 1):\n#             for col in range(1, len(text1) + 1):\n#                 if text2[row - 1] == text1[col - 1]:\n#                     dp[row][col] = dp[row-1][col-1] + 1\n#                 else:\n#                     dp[row][col] = max(dp[row-1][col], dp[row][col-1])\n        \n#         return dp[-1][-1]\n        from functools import lru_cache\n\n        @lru_cache(maxsize=None)\n        def lcs(i, j):\n            if i == len(text1) or j == len(text2):\n                return 0\n            elif text1[i] ==  text2[j]:\n                r = 1 + lcs(i + 1, j + 1)\n            else:\n                r = max(lcs(i + 1, j), lcs(i, j + 1))\n                \n            return r\n        \n        return lcs(0, 0)", "class Solution:\n    def longestCommonSubsequence(self, s1: str, s2: str) -> int:\n        \n        @lru_cache(None)\n        def helper(i, j):\n            if i == len(s1) or j == len(s2):\n                return 0\n            if s1[i] == s2[j]:\n                return 1 + helper(i + 1, j + 1)\n            else:\n                return max(helper(i+1, j), helper(i, j + 1))\n        return helper(0,0)\n", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        \n        @lru_cache(maxsize=None)\n        def memo_solve(p1, p2):\n            \n            # Base case: If either string is now empty, we can't match\n            # up anymore characters.\n            if p1 == len(text1) or p2 == len(text2):\n                return 0\n            \n            # Recursive case 1.\n            if text1[p1] == text2[p2]:\n                return 1 + memo_solve(p1 + 1, p2 + 1)\n            \n            # Recursive case 2.\n            else:\n                return max(memo_solve(p1, p2 + 1), memo_solve(p1 + 1, p2))\n            \n        return memo_solve(0, 0)", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        \n        \n        n = len(text1)\n        m = len(text2)\n        \n        self.store = [[-1 for i in range(m)] for j in range(n)]\n       \n        self.Rec(text1,text2,n-1,m-1)\n        \n        return self.store[-1][-1]\n    \n    def Rec(self, text1, text2,n,m):\n        \n        \n        if(n < 0 or m < 0):\n            return 0\n        \n        if(self.store[n][m] != -1):\n            return self.store[n][m]\n        \n        if(text1[n] == text2[m]):\n            \n            x = 1+self.Rec(text1,text2,n-1,m-1)\n            \n            self.store[n][m] = x\n        \n        else:\n            x = max(self.Rec(text1,text2,n-1,m), self.Rec(text1,text2,n,m-1))\n            \n            self.store[n][m] = x\n        \n        return x", "from functools import lru_cache\nclass Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        \n        @lru_cache(maxsize=None)\n        def memo_solve(p1, p2):\n            \n            # Base case: If either string is now empty, we can't match\n            # up anymore characters.\n            if p1 == len(text1) or p2 == len(text2):\n                return 0\n            \n            # Recursive case 1.\n            if text1[p1] == text2[p2]:\n                return 1 + memo_solve(p1 + 1, p2 + 1)\n            \n            # Recursive case 2.\n            else:\n                return max(memo_solve(p1, p2 + 1), memo_solve(p1 + 1, p2))\n            \n        return memo_solve(0, 0)", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        def lcs(i,j):\n            if i==len(text1) or j==len(text2):\n                return 0\n            if dp[i][j]!=None:\n                return dp[i][j]\n            if text1[i]==text2[j]:\n                dp[i][j]=1+lcs(i+1,j+1)\n                return dp[i][j]\n            dp[i][j]=max(lcs(i+1,j),lcs(i,j+1))\n            return dp[i][j]\n        dp=[[None for i in range(len(text2))] for j in range(len(text1))]\n        # print(dp)\n        # text1+=\\\"0\\\"\n        # text2+=\\\"0\\\"\n        lcs(0,0)\n        return dp[0][0]", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        \n#         h = {}\n#         def longest(t1, t2):\n#             if (t1, t2) in h:\n#                 return h[(t1, t2)]\n#             if not t1 or not t2:\n#                 h[(t1, t2)] = 0\n#                 return h[(t1, t2)]\n#             elif t1[0] == t2[0]:\n#                 h[(t1, t2)] = 1 + longest(t1[1:], t2[1:])\n#                 return h[(t1, t2)]\n#             else:\n#                 h[(t1, t2)] = max(longest(t1, t2[1:]), longest(t1[1:], t2))\n#                 return h[(t1, t2)]\n            \n#         return longest(text1, text2)\n\n        @lru_cache(None)\n        def longest(i, j):\n            if i == len(text1) or j == len(text2):\n                return 0\n            elif text1[i] == text2[j]:\n                return 1 + longest(i+1, j+1)\n            else:\n                return max(longest(i, j+1), longest(i+1, j))\n        \n        return longest(0, 0)", "from functools import lru_cache as memoize\n\nclass Solution():\n    def longestCommonSubsequence(self, text1, text2):\n        @memoize(None)\n        def lcs(s1,s2,m,n):\n            \n            if(m==0 or n==0):\n                return 0\n            \n            if s1[m-1] == s2[n-1]:\n                return 1 + lcs(s1,s2,m-1,n-1)\n            \n            else:\n                \n                return max(lcs(s1,s2,m-1,n),lcs(s1,s2,m,n-1))\n            \n            \n        return lcs(text1,text2,len(text1),len(text2))", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        # if len(text2)>len(tex)\n        \n        memorize = [[-1] * (len(text2)+1) for _ in range(len(text1)+1)]\n        def LCS(i1, i2):\n            if i1 >= len(text1) or i2 >= len(text2): return 0\n            if memorize[i1][i2]!=-1: return memorize[i1][i2]\n            \n            if text1[i1] == text2[i2]:\n                memorize[i1][i2] = 1 + LCS(i1+1, i2+1)\n            else:\n                memorize[i1][i2] = max(LCS(i1,i2+1), LCS(i1+1,i2))\n            return memorize[i1][i2]\n        \n        ans = LCS(0,0)\n        return ans\n#     def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n#         # if len(text2)>len(tex)\n        \n#         memorize = [[-1] * (len(text2)+1) for _ in range(len(text1)+1)]\n#         def LCS(i1, i2):\n#             if i1 >= len(text1) or i2 >= len(text2): return 0\n            \n#             if memorize[i1+1][i2]==-1:\n#                 memorize[i1+1][i2] = LCS(i1+1, i2)  \n#             option1 = memorize[i1+1][i2]\n            \n            \n#             first_occurence = text2.find(text1[i1], i2)\n            \n#             if first_occurence != -1:\n#                 if memorize[i1+1][i2+1]==-1:\n#                     memorize[i1+1][first_occurence+1] = LCS(i1+1, first_occurence+1)\n#                 option2 = 1 + memorize[i1+1][first_occurence+1]\n#             else: option2 = 0\n            \n            \n#             return max(option1, option2)\n#         ans = LCS(0,0)\n#         return ans\n            \n", "from functools import lru_cache\n\nclass Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        \n        @lru_cache(maxsize=None)\n        def memo_solve(p1,p2):\n            n = len(text1)\n            m = len(text2)\n            if n==p1 or m==p2:\n                return 0\n\n            # case1 = memo_solve(p1+1,p2)\n            # index = text2.find(text1[p1],p2)\n            # if index !=-1:\n            #     case2 = 1+memo_solve(p1+1,index+1)\n            # else:\n            #     case2 = 0\n            \n            if text1[p1]==text2[p2]:\n                return 1 + memo_solve(p1+1,p2+1)\n\n            return max(memo_solve(p1+1,p2),memo_solve(p1,p2+1))\n        return memo_solve(0,0)\n", "from typing import List\n\n\nclass Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n\n        # dp[i][j] \u8868\u793a text1[0:i+1] \u548c text2[0:j+1] \u7684 Longest Common Subsequence \u7684\u957f\u5ea6\n        # \u5176\u4e2d 0 <= i < len(text1)\n        # \u5176\u4e2d 0 <= j < len(text2)\n        dp: List[List[int]] = []\n        for i in range(len(text1)):\n            dp.append(len(text2) * [-1])\n\n        def cal_with_cache(i: int, j: int):\n            if i < 0 or j < 0:\n                return 0\n\n            if dp[i][j] == -1:\n                dp[i][j] = cal(i, j)\n            return dp[i][j]\n\n        def cal(i: int, j: int):\n            if i == 0 and j == 0:\n                return 1 if text1[i] == text2[j] else 0\n\n            if text1[i] == text2[j]:\n                return cal_with_cache(i - 1, j - 1) + 1\n            else:\n                return max(cal_with_cache(i - 1, j), cal_with_cache(i, j - 1))\n\n        return cal_with_cache(len(text1) - 1, len(text2) - 1)\n\n", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        \n        dp = defaultdict(int)\n        for i, c1 in enumerate(text1):\n            for j, c2 in enumerate(text2):\n                dp[i,j]  = max(dp[i-1, j-1] + (c1==c2), dp[i-1,j], dp[i,j-1])\n                \n        return dp[len(text1)-1, len(text2)-1]", "from functools import lru_cache\nclass Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        @lru_cache(None)\n        def dp(i,j,strx,stry):\n            if i>=len(strx) or j>=len(stry):\n                return 0\n            elif strx[i]==stry[j]:\n                return 1+dp(i+1,j+1,strx,stry)\n            else:\n                return max(dp(i,j+1,strx,stry),dp(i+1,j,strx,stry))\n        return dp(0,0,text1,text2)\n\n\n", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        m, n = len(text1), len(text2)\n        memo = [[-1 for _ in range(n)] for _ in range(m)]\n        return self.lcs(text1, 0, text2, 0, memo)\n    \n    def lcs(self, t1, i, t2, j, memo):\n        if i >= len(t1) or j >= len(t2): return 0\n        elif memo[i][j] != -1: return memo[i][j]\n        else:\n            result = -1\n            if t1[i] == t2[j]:\n                result = 1 + self.lcs(t1, i+1, t2, j+1, memo)\n            else:\n                result = max(self.lcs(t1, i+1, t2, j, memo), self.lcs(t1, i, t2, j+1, memo))\n            memo[i][j] = result\n            return result", "class Solution:\n    def longestCommonSubsequence(self, s1: str, s2: str) -> int:\n        \n        @lru_cache(None)\n        def helper(s1, s2, i, j):\n            if i == len(s1) or j == len(s2):\n                return 0\n            if s1[i] == s2[j]:\n                return 1 + helper(s1, s2, i + 1, j + 1)\n            else:\n                return max(helper(s1, s2, i+1, j), helper(s1, s2, i, j + 1))\n        return helper(s1,s2,0,0)\n", "from functools import lru_cache\n\nclass Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        if len(text1) == 0 or len(text2) == 0:\n            return 0\n        \n        t1_idx = len(text1) - 1\n        t2_idx = len(text2) - 1\n        \n        @lru_cache(maxsize=2147483647)\n        def lcs(t1_idx, t2_idx):\n            if t1_idx == -1 or t2_idx == -1:\n                return 0\n            if text1[t1_idx] == text2[t2_idx]:\n                return 1 + lcs(t1_idx - 1, t2_idx - 1)\n            else:\n                return max(lcs(t1_idx, t2_idx - 1), lcs(t1_idx - 1, t2_idx))\n        \n        return lcs(t1_idx, t2_idx)", "class Solution:\n    # def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n    #     matrix = [[None]*(len(text2)+1) for i in range(len(text1)+1)]\n    #     for j in range(len(text2)+1):\n    #         matrix[0][j] = 0\n    #     for i in range(len(text1)+1):\n    #         matrix[i][0] = 0\n    #     for i in range(1, len(text1)+1):\n    #         for j in range(1, len(text2)+1):\n    #             if text1[i-1] == text2[j-1]:\n    #                 matrix[i][j] = 1 + matrix[i-1][j-1]\n    #             else:\n    #                 matrix[i][j] = max(matrix[i-1][j], matrix[i][j-1])\n    #     return matrix[len(text1)][len(text2)]\n    \n    \n    \n    \n    \n    \n\n    \n    \n    \n\n\n    def longestCommonSubsequence(self, s1, s2):\n        def _longest_common_subsequence(i, j, cache):\n            p = (i, j)\n            if p in cache:\n                return cache[p]\n            elif i < 0 or j < 0:\n                return 0\n            elif s1[i] == s2[j]:\n                answer = 1 + _longest_common_subsequence(i-1, j-1, cache)\n                cache[p] = answer\n                return answer\n            else:\n                answer = max(_longest_common_subsequence(i, j-1, cache), _longest_common_subsequence(i-1, j, cache))\n                cache[p] = answer\n                return answer\n        return _longest_common_subsequence(len(s1)-1, len(s2)-1, {})", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        memo = [[ -1 for i in range(len(text2))] for i in range (len(text1))]\n        \n        def memoSolve(i, j) :\n            if i == len(text1) or j == len(text2):\n                return 0\n            \n            if memo[i][j] >= 0:\n                return memo[i][j]\n            \n            answer = 0\n            if text1[i] == text2[j]:\n                answer = 1+ memoSolve(i+1, j+1)\n            else:\n                answer = max(memoSolve(i+1,j), memoSolve(i,j+1))\n            memo[i][j] = answer\n            return memo[i][j]\n            \n        return memoSolve(0,0)", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        if not text1 or not text2: return 0\n        mem1 = [0] * (len(text2) + 1)\n        mem2 = [0] * (len(text2) + 1)\n        for i in range(len(text1)):\n            for j in range(len(text2)):\n                if text1[i] == text2[j]:\n                    mem2[j+1] = mem1[j] + 1\n                else:\n                    mem2[j+1] = max(mem2[j], mem1[j+1])\n            mem1 = mem2\n            mem2 = [0] * (len(text2) + 1)\n        return mem1[-1]\n\n        \n        \n        \n        \n        \n", "class Solution:\n    def __init__(self):\n        self.dp = None\n        \n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        self.dp = [[-1] * (len(text2) + 1) for _ in range(len(text1) + 1)]\n        return self.lcs_rec(text1, text2, len(text1), len(text2))\n        \n    def lcs_rec(self, x, y, n, m):\n        # Base Condition\n        if n == 0 or m == 0:\n            return 0\n        \n        # Memoization\n        if self.dp[n][m] != -1:\n            return self.dp[n][m]\n        \n        # Choice for subsequence\n        if x[n - 1] == y[m - 1]:\n            self.dp[n][m] = 1 + self.lcs_rec(x, y , n - 1, m - 1)\n        else:\n            self.dp[n][m] =  max(self.lcs_rec(x, y, n - 1, m), self.lcs_rec(x, y, n, m - 1))\n        return self.dp[n][m]", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        def s(i, j, cache):\n            p = (i,j)\n            if p not in cache:\n                if text1[i] == text2[j]:\n                    cache[p] = 1 + s(i-1, j-1, cache)\n                else:\n                    cache[p] = max(s(i, j-1, cache), s(i-1, j, cache))\n            return cache[p]\n        cache = {(-1, i): 0 for i in range(len(text2))}\n        for i in range(len(text1)):\n            cache[(i, -1)] = 0\n        cache[(-1, -1)] = 0\n        return s(len(text1)-1, len(text2)-1, cache)", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        @lru_cache(None)\n        def dfs(i, j):\n            if i < 0 or j < 0: return 0\n            if text1[i] == text2[j]: return 1+dfs(i-1, j-1)\n            return max(dfs(i, j-1), dfs(i-1, j))\n        \n        if not(text1 and text2): return 0\n        n, m = len(text1), len(text2)\n        return dfs(n-1, m-1)\n", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        dp = [[0 for i in range(len(text2))] for j in range(len(text1))]\n        \n        for i in range(len(text1)):\n            for j in range(len(text2)):\n                if text1[i] == text2[j]:\n                    dp[i][j] = (dp[i-1][j-1] if i>0 and j>0 else 0) + 1\n                else:\n                    p1 = dp[i-1][j] if i >0 else 0\n                    p2 = dp[i][j-1] if j > 0 else 0\n                    p3 = dp[i-1][j-1] if i>0 and j>0 else 0\n                    max_num = max(p1,p2,p3)\n                    dp[i][j] = max_num\n        return dp[-1][-1]", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        if not text1 or not text2:\n            return 0\n        \n\n        cacheRow = [None] * len(text2)\n        cache = [cacheRow[:] for i in range(len(text1))]\n        return self.dp(text1, text2, 0, 0, cache)\n        \n    \n    def dp(self, text1, text2, i, j, cache):\n        if i >= len(text1) or j >= len(text2):\n            return 0\n        \n        if cache[i][j] is None:\n            if text1[i] == text2[j]:\n                cache[i][j] = 1 + self.dp(text1, text2, i+1, j+1, cache)\n            else:\n                cache[i][j] = max(self.dp(text1, text2, i+1, j, cache), self.dp(text1, text2, i, j+1, cache))\n        \n        return cache[i][j]", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        def s(i, j):\n            p = (i,j)\n            if p not in cache:\n                if text1[i] == text2[j]:\n                    cache[p] = 1 + s(i-1, j-1)\n                else:\n                    cache[p] = max(s(i, j-1), s(i-1, j))\n            return cache[p]\n        cache = {(-1, i): 0 for i in range(len(text2))}\n        for i in range(len(text1)):\n            cache[(i, -1)] = 0\n        cache[(-1, -1)] = 0\n        return s(len(text1)-1, len(text2)-1)", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        if not text1 or not text2:\n            return 0\n        n1 = len(text1)\n        n2 = len(text2)\n        dp = [[0 for _ in range(n2 + 1)] for _ in range(2)]\n        \n        for i in range(n1 + 1):\n            for j in range(n2 + 1):\n                if i == 0 or j == 0:\n                    dp[i % 2][j] = 0\n                else:\n                    if text1[i - 1] == text2[j - 1]:\n                        dp[i % 2][j] = dp[1 - i % 2][j - 1] + 1\n                    else:\n                        dp[i % 2][j] = max(dp[1 - i % 2][j], dp[i % 2][j - 1])\n        return dp[n1 % 2][n2]\n", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        \n        # Create dp 2D array\n        dp = [[-1] * (len(text2)) for _ in range(len(text1))]\n\n        # Recursive helper function\n        def lcsForCell(i, j):\n            # Boundary conditions\n            if (i < 0) or (j < 0):\n                return 0\n\n            if dp[i][j] != -1:\n                return dp[i][j]\n\n            # If letters are the same\n            if text1[i] == text2[j]:\n                dp[i][j] = lcsForCell(i-1, j-1) + 1\n\n            else:\n                dp[i][j] = max(lcsForCell(i-1, j), lcsForCell(i, j-1))\n\n            return dp[i][j]\n        \n        return lcsForCell(len(text1)-1, len(text2)-1)\n        \n                \n", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        if len(text1) < len(text2):\n            text1, text2 = text2, text1\n        \n        prev = [0] * (len(text2) + 1)\n        curr = [0] * (len(text2) + 1)\n        \n        for row in range(len(text1)):\n            for col in range(len(text2)):\n                if text1[row] == text2[col]:\n                    curr[col + 1] = 1 + prev[col]\n                else:\n                    curr[col + 1] = max(prev[col + 1], curr[col])\n                    \n            prev, curr = curr, prev\n                    \n        return prev[-1]", "'''\nThe subproblem here is: suffixes\n\n\\\"abcde\\\"\n\\\"ce\\\"\n\nSo becase first letter \\\"a\\\" is in both text, its 1 plus the lcs of \\\"bcde\\\" and \\\"ace\\\"\n\nif its not the same however, we try take suffix of both and see which one matches, we return longest \n\n\n'''\nclass Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        n1 = len(text1)\n        n2 = len(text2)\n        \n        memo = {}\n        def lcs(pointer1, pointer2):\n            if (pointer1, pointer2) in memo: return memo[(pointer1, pointer2)]\n            if pointer1 >= n1 or pointer2 >= n2: return 0\n            if text1[pointer1] == text2[pointer2]:\n                # move on to the next\n                x =  1 + lcs(pointer1 + 1, pointer2 + 1)\n            else:\n                x =  max(lcs(pointer1 + 1, pointer2), lcs(pointer1, pointer2+1))\n            memo[(pointer1, pointer2)] = x\n            return x\n            \n            \n        return lcs(0,0)\n            \n            \n            \n", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        '''\n        f[i][j]: \u524di\u4e2a\uff0c\u524dj\u4e2a\u5339\u914d\u7684\u6700\u957f\n        '''\n        m, n = len(text1), len(text2)\n        f = [[0] * (n+1) for _ in range(m+1)]\n        for i in range(m+1):\n            for j in range(n+1):\n                if i == 0 and j == 0:\n                    f[i][j] = 0\n                elif i == 0:\n                    f[i][j] = 0\n                elif j == 0:\n                    f[i][j] = 0\n                else:\n                    if text1[i-1] == text2[j-1]:\n                        f[i][j] = max(f[i][j-1], f[i-1][j], f[i-1][j-1] + 1)\n                    else:     \n                        f[i][j] = max(f[i][j-1], f[i-1][j])\n                        \n        return f[m][n]", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        def solve(i, j):\n            # Base case: reached end of one of the strings\n            if i == n or j == m:\n                return 0\n            \n            # Memoization case\n            if memo[i][j] != -1:\n                return memo[i][j]\n            \n            # Recursive case 1: text1[i] == text2[j]\n            if text1[i] == text2[j]:\n                memo[i][j] = 1 + solve(i+1, j+1)\n                \n            # Recursive case 2: text1[i] != text2[j]\n            else:\n                memo[i][j] = max(solve(i, j+1), solve(i+1, j))\n            \n            return memo[i][j]\n        \n        n, m = len(text1), len(text2)\n        \n        memo = [[-1 for _ in range(m)] for _ in range(n)]\n        \n        return solve(0, 0)\n            \n", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        memo = [[-1] * (len(text2) + 1) for _ in range(len(text1) + 1)]\n        def dfs(t1, t2):\n            n1, n2 = len(t1), len(t2)\n            if memo[n1][n2] != -1:\n                return memo[n1][n2]\n            if n1 == 0 or n2 == 0:\n                return 0\n            \n            if t1[-1] == t2[-1]:\n                res = dfs(t1[:-1], t2[:-1]) + 1\n            else:\n                res = max(dfs(t1[:-1], t2), dfs(t1, t2[:-1]))\n            memo[n1][n2] = res\n            return res\n        dfs(text1, text2)\n        return memo[-1][-1]", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        def s(i, j, cache):\n            p = (i,j)\n            if p not in cache:\n                c = 0\n                while i >= 0 and j >= 0 and text1[i] == text2[j]:\n                    c += 1\n                    i -= 1\n                    j -= 1\n                if c > 0:\n                    cache[p] = c + s(i, j, cache)\n                else:\n                    cache[p] = max(s(i, j-1, cache), s(i-1, j, cache))\n            return cache[p]\n        cache = {(-1, i): 0 for i in range(len(text2))}\n        for i in range(len(text1)):\n            cache[(i, -1)] = 0\n        cache[(-1, -1)] = 0\n        return s(len(text1)-1, len(text2)-1, cache)", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        self.n = len(text1)\n        self.m = len(text2)\n        self.text1 = text1\n        self.text2 = text2\n        self.table = []\n        for i in range(self.n):\n            self.table.append([-1] * self.m)\n        return self.longest(0,0)\n            \n    def longest(self, i, j):\n        if (i == self.n) or (j == self.m):\n            return 0\n        if self.table[i][j] != -1:\n            return self.table[i][j]\n        else:\n            if self.text1[i] == self.text2[j]:\n                self.table[i][j] = 1 + self.longest(i+1, j+1)\n            else:\n                self.table[i][j] = max(self.longest(i+1, j), self.longest(i, j+1))\n            return self.table[i][j]\n            \n", "from functools import lru_cache\n\nclass Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        \n#         @lru_cache(maxsize=None)\n#         def recur(n,m):\n            \n#             if n == len(text1) or m == len(text2):\n#                 return 0\n            \n#             if text1[n] == text2[m]:\n#                 return 1 + recur(n+1,m+1)\n            \n#             else:\n            \n#                 return max(recur(n,m+1),recur(n+1,m))\n                \n        \n#         return recur(0,0)\n        \n    #    '' a b c d e\n    # '' 0  0 0 0 0 0 \n    # a  0  1 1 1 1 1\n    # c  0  1 1 2 2 2\n    # e  0  1 1 2 2 3\n    \n        # dp = [[0]*(len(text1)+1) for _ in range(len(text2)+1)]\n        \n        previous = [0] * (len(text1) + 1)\n        current = [0] * (len(text1) + 1)\n        # print(len(dp),len(dp[0]))\n        \n        for i in range(1,len(text2)+1):\n            for j in range(1,len(text1)+1):\n                \n                if text2[i-1] == text1[j-1]:\n                    \n                    current[j] = previous[j-1] + 1\n                else:\n                    current[j] = max(current[j-1], previous[j])\n                \n            previous = current\n            current = [0] * (len(text1) + 1)\n                \n        return previous[-1]\n\n\n\n\n\n\n\n\n\n#         dp_grid = [[0]*(len(text1)+1) for _ in range(len(text2)+1)]\n      \n#         for row in range(len(text2)):\n#             for col in range(len(text1)):\n#                 # print(row,col)\n#                 if text1[col] == text2[row]:\n#                     dp_grid[row+1][col+1] = 1 + dp_grid[row][col]\n#                 else:\n#                     dp_grid[row+1][col+1] = max(dp_grid[row][col+1],dp_grid[row+1][col])\n        \n#         return dp_grid[len(text2)][len(text1)]\n                    \n", "class Solution:\n    def longestCommonSubsequence(self, s1: str, s2: str) -> int:\n      dp = [[0] * (len(s2) + 1) for _ in range(len(s1) + 1)]\n\n      # s1: row\n      # s2: col\n      for s1_index in range(len(s1)):\n        for s2_index in range(len(s2)):\n          if s1[s1_index] != s2[s2_index]:\n            dp[s1_index + 1][s2_index + 1] = max(dp[s1_index][s2_index + 1],\n                                                 dp[s1_index + 1][s2_index],\n                                                 dp[s1_index][s2_index])\n          else:\n            dp[s1_index + 1][s2_index + 1] = max(dp[s1_index][s2_index + 1],\n                                                 dp[s1_index + 1][s2_index],\n                                                 dp[s1_index][s2_index] + 1)\n      return dp[-1][-1]", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        @lru_cache(maxsize=None)\n        def memo_solve(p1, p2):\n            \n            # Base case: If either string is now empty, we can't match\n            # up anymore characters.\n            if p1 == len(text1) or p2 == len(text2):\n                return 0\n            \n            # Option 1: We don't include text1[p1] in the solution.\n            option_1 = memo_solve(p1 + 1, p2)\n            \n            # Option 2: We include text1[p1] in the solution, as long as\n            # a match for it in text2 at or after p2 exists.\n            first_occurence = text2.find(text1[p1], p2)\n            option_2 = 0\n            if first_occurence != -1:\n                option_2 = 1 + memo_solve(p1 + 1, first_occurence + 1)\n            \n            # Return the best option.\n            return max(option_1, option_2)\n                \n        return memo_solve(0, 0)", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        def s(i, j, cache):\n            if i < 0 or j < 0:\n                return 0\n            p = (i,j)\n            if p not in cache:\n                if text1[i] == text2[j]:\n                    cache[p] = 1 + s(i-1, j-1, cache)\n                else:\n                    cache[p] = max(s(i, j-1, cache), s(i-1, j, cache))\n            return cache[p]\n        cache = {}\n        # cache = {(-1, i): 0 for i in range(len(text2))}\n        # for i in range(len(text1)):\n        #     cache[(i, -1)] = 0\n        # cache[(-1, -1)] = 0\n        return s(len(text1)-1, len(text2)-1, cache)", "class Solution:\n    def lcs(self, text1, text2, i1, i2, memo):\n        if len(text1) == i1 or len(text2) == i2:\n            return 0\n        \n        if memo[i1][i2] != -1:\n            return memo[i1][i2]\n        \n        if text1[i1] == text2[i2]:\n            memo[i1][i2] = 1 + self.lcs(text1, text2, i1 + 1, i2 + 1, memo)\n            return memo[i1][i2]\n        \n        maxLen = 0\n        maxLen = max(maxLen, self.lcs(text1, text2, i1 + 1, i2, memo))\n        maxLen = max(maxLen, self.lcs(text1, text2, i1, i2 + 1, memo))\n        memo[i1][i2] = maxLen\n        \n        return maxLen\n        \n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        memo = [[-1 for _ in range(len(text2))] for _ in range(len(text1))]\n        maxLen = self.lcs(text1, text2, 0, 0, memo)\n        return maxLen", "class Solution:\n    def lcs(self, s1, s2, m, n):\n        if m == 0 or n == 0:\n            return 0\n        if self.dp[m][n] != -1: return self.dp[m][n]\n        if s1[m - 1] == s2[n - 1]:\n            self.dp[m][n] = 1 + self.lcs(s1, s2, m - 1, n - 1)\n        else:\n            self.dp[m][n] = max(self.lcs(s1, s2, m - 1, n), self.lcs(s1, s2, m, n - 1))\n        return self.dp[m][n]\n\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        m = len(text1)\n        n = len(text2)\n        self.dp = [[-1 for _ in range(n + 1)] for __ in range(m + 1)]\n        return self.lcs(text1, text2, m, n)\n", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        mem = {}\n        def dfs(l, r):\n            if((l, r) in mem):\n                return mem[(l, r)]\n            if(l == len(text1) or r == len(text2)):\n                return 0\n            ans = 0\n            if(text1[l] == text2[r]):\n                ans = 1+dfs(l+1, r+1)\n            else:\n                ans = max(dfs(l+1, r), dfs(l, r+1))\n            mem[(l, r)] = ans\n            return ans\n        return dfs(0, 0)", "'''\n     text2 a c e\n         0 1 2 3\ntext1 0  0 0 0 0\n    a 1  0 1 1 1\n    b 2  0 1 1 1\n    c 3  0 1 2 2\n    d 4  0 1 2 2\n    e 5  0 1 2 3\n'''\n\nclass Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        # dp[i][j] reprents the length of the longest common subsequence for text1[:i] and text2[:j]\n        m, n = len(text1) + 1, len(text2) + 1\n        dp = [[0] * n for _ in range(m)]\n        res = 0\n        for i in range(1, m):  # start from one char\n            for j in range(1, n):\n                if text1[i-1] == text2[j-1]:\n                    dp[i][j] = dp[i-1][j-1] + 1\n                else:\n                    dp[i][j] = max(dp[i][j-1], dp[i-1][j])\n                res = max(res, dp[i][j])                                                        \n        return res", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n#         dp = [[0] * (len(text1) + 1) for _ in range(len(text2) + 1)]\n        \n#         # logic: if same, add 1, else max(try each without first)\n#         # if row,col V == same, == prev diag + 1\n#         # else: = max(row-1,col, row,col-1)\n        \n#         for row in range(1, len(text2) + 1):\n#             for col in range(1, len(text1) + 1):\n#                 if text2[row - 1] == text1[col - 1]:\n#                     dp[row][col] = dp[row-1][col-1] + 1\n#                 else:\n#                     dp[row][col] = max(dp[row-1][col], dp[row][col-1])\n        \n#         return dp[-1][-1]\n        from functools import lru_cache\n\n        memo = {}\n        def lcs(i, j):\n            if (i, j) in memo:\n                return memo[(i, j)]\n            if i == len(text1) or j == len(text2):\n                r = 0\n            elif text1[i] ==  text2[j]:\n                r = 1 + lcs(i + 1, j + 1)\n            else:\n                r = max(lcs(i + 1, j), lcs(i, j + 1))\n                \n            memo[(i, j)] = r\n            return r\n        \n        return lcs(0, 0)", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        if len(text1) <= len(text2) :\n            ss, ls = text1, text2\n        else :\n            ss, ls = text2, text1\n        track = [0] * len(ss)\n        \n        \n        for i2 in range(0, len(ls)) :\n            prev = track[0]\n            if ls[i2] == ss[0] :\n                track[0] = 1\n            for i1 in range(1, len(ss)) :\n                newPrev = track[i1]\n                if ls[i2] == ss[i1] :\n                    track[i1] = prev + 1\n                else :\n                    track[i1] = max(track[i1], track[i1-1])\n                prev = newPrev\n        return track[-1]\n                \n            \n", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        dp = {}\n        \n        def lcs(left, right):\n            nonlocal text1\n            nonlocal text2\n            if (left, right) in dp:\n                return dp[(left, right)]\n            if left >= len(text1) or right >= len(text2):\n                return 0\n            if text1[left] == text2[right]:\n                count = 1 + lcs(left + 1, right + 1)\n                dp[(left, right)] = count\n                return count\n            else:\n                count = max(lcs(left + 1, right), lcs(left, right + 1))\n                dp[(left, right)] = count\n                return count\n        return lcs(0, 0)", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        memo = {}\n        def dpRecurse(i : int, j : int):\n            result = 0\n            if (i, j) in memo:\n                return memo[(i, j)]\n            \n            if i >= len(text1) or j >= len(text2):\n                return 0;\n            elif text1[i] == text2[j]:\n                result = 1 + dpRecurse(i + 1, j + 1)\n            else:\n                result = max(dpRecurse(i + 1, j), dpRecurse(i, j + 1))\n            memo[(i, j)] = result\n            return result\n            \n        return dpRecurse(0, 0)\n", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        from functools import lru_cache\n        @lru_cache(maxsize=None)\n        def memo_solve(p1, p2):\n            \n            # Base case: If either string is now empty, we can't match\n            # up anymore characters.\n            if p1 == len(text1) or p2 == len(text2):\n                return 0\n            \n            # Option 1: We don't include text1[p1] in the solution.\n            option_1 = memo_solve(p1 + 1, p2)\n            \n            # Option 2: We include text1[p1] in the solution, as long as\n            # a match for it in text2 at or after p2 exists.\n            first_occurence = text2.find(text1[p1], p2)\n            option_2 = 0\n            if first_occurence != -1:\n                option_2 = 1 + memo_solve(p1 + 1, first_occurence + 1)\n            \n            # Return the best option.\n            return max(option_1, option_2)\n                \n        return memo_solve(0, 0)", "from functools import lru_cache\n\nclass Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        \n        @lru_cache(maxsize=None)\n        def memo_solve(p1, p2):\n            \n            # Base case: If either string is now empty, we can't match\n            # up anymore characters.\n            if p1 == len(text1) or p2 == len(text2):\n                return 0\n            \n            # Option 1: We don't include text1[p1] in the solution.\n            option_1 = memo_solve(p1 + 1, p2)\n            \n            # Option 2: We include text1[p1] in the solution, as long as\n            # a match for it in text2 at or after p2 exists.\n            first_occurence = text2.find(text1[p1], p2)\n            option_2 = 0\n            if first_occurence != -1:\n                option_2 = 1 + memo_solve(p1 + 1, first_occurence + 1)\n            \n            # Return the best option.\n            return max(option_1, option_2)\n                \n        return memo_solve(0, 0)", "from functools import lru_cache\n\n\nclass Solution:\n    def longestCommonSubsequence(self, txt1: str, txt2: str) -> int:\n        @lru_cache(maxsize=None)\n        def rec(i, j):\n            if i == -1 or j == -1:\n                return 0\n            if txt1[i] == txt2[j]:\n                return rec(i-1, j-1) + 1\n            if txt1[i] != txt2[j]:\n                return max(rec(i-1, j), rec(i, j-1))\n            \n        return rec(len(txt1) - 1, len(txt2) - 1)\n", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        memo = {}\n        def dpRecurse(i : int, j : int):\n            result = 0\n            if (i, j) in memo:\n                return memo[(i, j)]\n            \n            if i >= len(text1) or j >= len(text2):\n                return 0;\n            elif text1[i] == text2[j]:\n                result = 1 + dpRecurse(i + 1, j + 1)\n            else:\n                result = max(dpRecurse(i + 1, j), dpRecurse(i, j + 1))\n            memo[(i, j)] = result\n            return result\n            \n        return dpRecurse(0, 0)", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        return self.lcs(text1, text2, len(text1) - 1, len(text2) - 1, {})\n\n    def lcs(self, text1, text2, i, j, memo):\n        if i < 0 or j < 0:\n            return 0\n        \n        if (i, j) in memo:\n            return memo[(i, j)]\n\n        if text1[i] == text2[j]:\n            return 1 + self.lcs(text1, text2, i - 1, j - 1, memo)\n        \n        memo[(i, j)] = max(\n            self.lcs(text1, text2, i - 1, j, memo),\n            self.lcs(text1, text2, i, j - 1, memo),\n        )\n        \n        return memo[(i, j)]", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        return self.find({}, 0, 0, text1, text2)\n    def find(self, memo, i, j, text1, text2):\n        if (i, j) in memo:\n            return memo[(i, j)]\n        if i == len(text1):\n            return 0\n        if j == len(text2):\n            return 0\n        if text1[i] == text2[j]:\n            memo[(i, j)] = self.find(memo, i+1, j+1, text1, text2) + 1\n        else:\n            memo[(i, j)] = max(self.find(memo, i, j+1, text1, text2), self.find(memo, i+1, j, text1, text2))\n        return memo[(i, j)]", "from functools import lru_cache\n\n\nclass Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        @lru_cache(maxsize=None)\n        def rec(txt1, txt2, len1, len2):\n\n            if len1 == 0 or len2 == 0:\n                return 0\n            if txt1[len1-1] == txt2[len2-1]:\n                return rec(txt1, txt2, len1-1, len2-1) + 1\n            else:\n                return max(rec(txt1, txt2, len1-1, len2), rec(txt1, txt2, len1, len2-1))\n        return rec(text1, text2, len(text1), len(text2))\n", "import math\n\nclass Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        m = len(text1)\n        n = len(text2)\n        \n        if m == 0 or n == 0:\n            return 0\n        \n        mat = [[-math.inf]*(n+1) for _ in range(m+1)]\n        prev = [0]*(n+1)\n        curr = [0] + [-math.inf]*n\n            \n        for a in range(1, m+1):\n            for b in range(1, n + 1):\n                if text1[a-1] == text2[b-1]:\n                    curr[b] = 1 + prev[b-1]\n                else:\n                    curr[b] = max(curr[b-1], prev[b])\n            \n            prev = curr\n            curr = [0] + [-math.inf]*n\n        \n        return prev[n]\n", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        memo = {}\n        return self.helper(0,0,text1,text2,memo)\n        \n    def helper(self,index_1,index_2,text1,text2,memo):\n        if (index_1 == len(text1) or index_2 == len(text2)):\n            return 0\n        elif (index_1,index_2) in memo:\n            return memo[(index_1,index_2)]\n        else:\n            if (text1[index_1] == text2[index_2]):\n                ans = 1 + self.helper(index_1 + 1,index_2 + 1,text1,text2,memo)\n            else:\n                ans = max(self.helper(index_1 + 1,index_2,text1,text2,memo),\n                          self.helper(index_1,index_2 + 1,text1,text2,memo))\n            memo[(index_1,index_2)] = ans\n            return ans\n", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        hist = {}\n        \n        def helper(str1, str2, m, n):\n            if (m, n) in hist:\n                return hist[(m, n)]\n            \n            if m == 0 or n == 0:\n                return 0\n            elif str1[m-1] == str2[n-1]:\n                hist[(m, n)] = 1 + helper(str1, str2, m-1, n-1)\n                return hist[(m, n)] \n            \n            hist[(m, n)] = max(\n                helper(str1, str2, m-1, n),\n                helper(str1, str2, m, n-1)\n            )\n            return hist[(m, n)]\n        return helper(text1, text2, len(text1), len(text2))", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        def _longest_common_subsequence(i, j):\n            if i < 0 or j < 0:\n                return 0\n            \n            if (i, j) not in mem:\n                if text1[i] != text2[j]:\n                    mem[(i, j)] = max(_longest_common_subsequence(i - 1, j), _longest_common_subsequence(i, j - 1))\n                else:\n                    mem[(i, j)] = _longest_common_subsequence(i - 1, j - 1) + 1\n            \n            return mem[(i, j)]\n        \n        mem = {}\n        return _longest_common_subsequence(len(text1) - 1, len(text2) - 1)\n", "from typing import List\n\n\nclass Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n\n        # dp[i][j] \u8868\u793a text1[0:i+1] \u548c text2[0:j+1] \u7684 Longest Common Subsequence \u7684\u957f\u5ea6\n        # \u5176\u4e2d 0 <= i < len(text1)\n        # \u5176\u4e2d 0 <= j < len(text2)\n        dp: List[List[int]] = []\n        for i in range(len(text1)):\n            dp.append(len(text2) * [-1])\n\n        def cal_with_cache(i: int, j: int):\n            if i < 0 or j < 0:\n                return 0\n\n            if dp[i][j] == -1:\n                dp[i][j] = cal(i, j)\n            return dp[i][j]\n\n        def cal(i: int, j: int):\n            if i == 0 and j == 0:\n                return 1 if text1[i] == text2[j] else 0\n\n            if text1[i] == text2[j]:\n                return cal_with_cache(i - 1, j - 1) + 1\n            else:\n                return max(cal_with_cache(i - 1, j), cal_with_cache(i, j - 1))\n\n        for i in range(len(text1)):\n            for j in range(len(text2)):\n                cal_with_cache(i, j)\n\n        return cal_with_cache(len(text1) - 1, len(text2) - 1)\n\n", "import numpy as np\nclass Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        \n        l1 = len(text1)\n        l2 = len(text2)\n        \n        dp = np.zeros((l1+1, l2+1), dtype = int)\n        \n    \n        dp[:][0] = 0\n        \n  \n        dp[0][:] = 0\n            \n        for i in range(1, l1+1):\n            for j in range(1, l2+1):\n                if text1[i-1] == text2[j-1]:\n                    dp[i][j] = 1 + dp[i-1][j-1]\n                else:\n                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])\n                    \n        return dp[-1][-1]\n        \n        \n", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        memo = {}\n        if not text1 or not text2:\n            return 0\n        def lcs(i,j):\n            if i == len(text1) or j == len(text2):\n                return 0\n            if (i,j) in memo:\n                return memo[(i,j)]\n            \n            if text1[i] == text2[j]:\n                ans = 1 + lcs(i+1,j+1)\n            else:\n                ans = max(lcs(i+1,j), lcs(i,j+1))\n            memo[(i,j)] = ans\n            return ans\n        \n        return lcs(0,0)", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n#         dp = [[0] * (len(text1) + 1) for _ in range(len(text2) + 1)]\n        \n#         # logic: if same, add 1, else max(try each without first)\n#         # if row,col V == same, == prev diag + 1\n#         # else: = max(row-1,col, row,col-1)\n        \n#         for row in range(1, len(text2) + 1):\n#             for col in range(1, len(text1) + 1):\n#                 if text2[row - 1] == text1[col - 1]:\n#                     dp[row][col] = dp[row-1][col-1] + 1\n#                 else:\n#                     dp[row][col] = max(dp[row-1][col], dp[row][col-1])\n        \n#         return dp[-1][-1]\n        from functools import lru_cache\n\n        memo = {}\n        def lcs(i, j):\n            if i == len(text1) or j == len(text2):\n                return 0\n            if (i, j) in memo:\n                return memo[(i, j)]\n            elif text1[i] ==  text2[j]:\n                r = 1 + lcs(i + 1, j + 1)\n            else:\n                r = max(lcs(i + 1, j), lcs(i, j + 1))\n                \n            memo[(i, j)] = r\n            return r\n        \n        return lcs(0, 0)", "import numpy as np\nclass Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        \n        l1 = len(text1)\n        l2 = len(text2)\n        \n        dp = np.zeros((l1+1, l2+1), dtype = int)\n        \n        for i in range(l1+1):\n            dp[i][0] = 0\n        \n        for i in range(l2+1):\n            dp[0][i] = 0\n            \n        for i in range(1, l1+1):\n            for j in range(1, l2+1):\n                if text1[i-1] == text2[j-1]:\n                    dp[i][j] = 1 + dp[i-1][j-1]\n                else:\n                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])\n                    \n        return dp[-1][-1]\n        \n        \n", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        memo = [[ -1 for i in range(len(text2))] for i in range (len(text1))]\n        \n        def memoSolve(i, j) :\n            if i == len(text1) or j == len(text2):\n                return 0\n            \n            if memo[i][j] >= 0:\n                return memo[i][j]\n            \n            include = 0\n            j2 = text2.find(text1[i], j)\n            if j2 != -1:\n                include = 1 + memoSolve(i + 1, j2 + 1)\n            noTake = memoSolve(i + 1, j)\n            \n            memo[i][j] = max(include, noTake)\n            return memo[i][j]\n            \n        return memoSolve(0,0)", "import math\n\nclass Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        m = len(text1)\n        n = len(text2)\n        \n        if m == 0 or n == 0:\n            return 0\n        \n        prev = [0]*(n+1)\n        curr = [0] + [-math.inf]*n\n            \n        for a in range(1, m+1):\n            for b in range(1, n + 1):\n                if text1[a-1] == text2[b-1]:\n                    curr[b] = 1 + prev[b-1]\n                else:\n                    curr[b] = max(curr[b-1], prev[b])\n            \n            prev = curr\n            curr = [0] + [-math.inf]*n\n        \n        return prev[n]\n", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        def helper(text1, text2,i,j,memo):\n            if i == len(text1) or j == len(text2):\n                return 0\n            if memo[i][j] < 0:\n                c1 = text1[i]\n                c2 = text2[j]\n                if c1 == c2:\n                    memo[i+1][j+1] = helper(text1,text2,i+1,j+1,memo)\n                    memo[i][j] = 1 + memo[i+1][j+1]\n                else:\n                    memo[i+1][j] = helper(text1,text2,i+1,j,memo)\n                    memo[i][j+1] = helper(text1,text2,i,j+1,memo)\n                    memo[i][j] = max(memo[i+1][j],memo[i][j+1])\n            return memo[i][j]\n        \n        n = len(text1)\n        m = len(text2)\n        memo = [[-1 for _ in range(0,m+1)] for _ in range(0,n+1)]\n        \n        \n        return helper(text1,text2,0,0,memo)", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n#         dp = [[0] * (len(text1) + 1) for _ in range(len(text2) + 1)]\n        \n#         # logic: if same, add 1, else max(try each without first)\n#         # if row,col V == same, == prev diag + 1\n#         # else: = max(row-1,col, row,col-1)\n        \n#         for row in range(1, len(text2) + 1):\n#             for col in range(1, len(text1) + 1):\n#                 if text2[row - 1] == text1[col - 1]:\n#                     dp[row][col] = dp[row-1][col-1] + 1\n#                 else:\n#                     dp[row][col] = max(dp[row-1][col], dp[row][col-1])\n        \n#         return dp[-1][-1]\n    \n        memo = {}\n        def lcs(i, j):\n            if i == len(text1) or j == len(text2):\n                return 0\n            if (i, j) in memo:\n                return memo[(i, j)]\n            elif text1[i] ==  text2[j]:\n                r = 1 + lcs(i + 1, j + 1)\n            else:\n                r = max(lcs(i + 1, j), lcs(i, j + 1))\n                \n            memo[(i, j)] = r\n            return r\n        \n        return lcs(0, 0)", "from functools import wraps\n\nclass Solution:\n    def longestCommonSubsequence(self, text1, text2):\n\n        def cache_decorator(f):\n            _cache = {}\n\n            @wraps(f)\n            def new_f(*args):\n                if args not in _cache:\n                    _cache[args] = f(*args)\n                return _cache[args]\n\n            return new_f\n\n        @cache_decorator\n        def compute(x, y):\n            if x == len(text1):\n                return 0\n            if y == len(text2):\n                return 0\n\n            if text1[x] == text2[y]:\n                return 1 + compute(x+1, y+1)\n\n            return max([compute(x+1, y), compute(x, y+1)])\n\n        return compute(0, 0)\n\n", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        \n        \n        def lcs_helper(index1, index2, memo = {}):\n        \n            if index1 == len(text1) or index2 == len(text2):\n                return 0\n            key = (index1, index2)\n            if key not in memo:\n\n                if text1[index1] == text2[index2]:\n                    memo[key] = 1 + lcs_helper(index1+1, index2+1, memo)\n                else:\n                    memo[key] =  max(lcs_helper(index1, index2+1,memo),\n                           lcs_helper(index1+1, index2, memo))\n            return memo[key]\n        \n        return lcs_helper(0,0)\n        \n    \n    \n    \n    \n    \n    \n    \n    \n    \n    \n    \n    \n    \n    \n    \n#     def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n#         max_count = float(\\\"-inf\\\")\n        \n#         for _ in range(len(text1)):\n#             curr_count = 0\n#             left_index = 0\n#             for index in range(_,len(text1)):\n#                 char = text1[index]\n#                 if text2.find(char, left_index) != -1:\n#                     curr_count +=1\n#                     left_index = text2.find(char, left_index) + 1\n#                     remaining_string = text2[left_index:]\n#             max_count = max(max_count, curr_count)\n                \n#         return max_count\n                \n                \n", "import numpy as np\nclass Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        \n        l1 = len(text1)\n        l2 = len(text2)\n        \n        dp = np.zeros((l1+1, l2+1), dtype = int)\n        \n        dp[:][0] = 0\n        dp[0][:] = 0\n            \n        for i in range(1, l1+1):\n            for j in range(1, l2+1):\n                if text1[i-1] == text2[j-1]:\n                    dp[i][j] = 1 + dp[i-1][j-1]\n                else:\n                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])\n                    \n        return dp[-1][-1]\n        \n        \n", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        cache = { }\n        \n        def dfs( i, j, count):\n            \n            if i == len(text1) or j == len(text2):\n                return 0\n            \n            if (i,j) in cache:\n                return cache[(i,j)]\n            \n            if text1[i] == text2[j]:\n                #count += 1\n                return 1 + dfs( i+1, j+1, count)\n                \n            a = dfs( i+1, j,   count  )\n            b = dfs( i,   j+1, count )\n            c = max(a,b)\n            \n            cache[(i,j)] = c\n            return c\n        \n        return dfs( 0, 0, 0 )\n", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        def helper(i, j):\n            if i == n1 or j==n2:\n                self.h[i,j] = 0\n                return 0\n            \n            if (i,j) in self.h:\n                return self.h[i,j]\n            \n            if text1[i]==text2[j]:\n                self.h[i,j] = helper(i+1, j+1)+1\n            else:\n                self.h[i,j] = max(helper(i+1, j), helper(i, j+1))\n            \n            return self.h[i,j]\n                \n        \n        n1 = len(text1)\n        n2 = len(text2)\n        \n        self.h = {}\n        \n        res = helper(0, 0)\n        \n        return res", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        memo = {}\n        def recurse(i1, i2):\n            if i1 >= len(text1) or i2 >= len(text2):\n                return 0\n            \n            if (i1, i2) in memo:\n                return memo[(i1, i2)]\n            \n            if text1[i1] == text2[i2]:\n                memo[(i1, i2)] = 1 + recurse(i1+1, i2+1)\n            else:\n                memo[(i1, i2)] = max(recurse(i1+1, i2), recurse(i1, i2+1))\n            \n            return memo[(i1, i2)]\n        \n        return recurse(0, 0)\n", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        \n        \n        if(len(text1) < len(text2)):\n            text1,text2 = text2,text1\n        \n        row = len(text2)\n        col = len(text1) + 1\n      \n        # dp = [[0 for _ in range(col)] for _ in range(row)]\n        \n        dp = [0 for _ in range(col)]\n        \n        for i in range(row):\n            pre = 0\n            for j in range(1,col):\n                \n                temp = dp[j]\n                if(text1[j-1] == text2[i]):\n                    dp[j] = pre + 1\n                    # dp[i][j] = dp[i-1][j-1] + 1\n                else:\n                    dp[j] = max(dp[j-1],dp[j])\n                    # dp[i][j] = max(dp[i-1][j],dp[i][j-1])\n                pre = temp\n        \n        return dp[-1]\n", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n#         dp = [[0] * (len(text1) + 1) for _ in range(len(text2) + 1)]\n        \n#         # logic: if same, add 1, else max(try each without first)\n#         # if row,col V == same, == prev diag + 1\n#         # else: = max(row-1,col, row,col-1)\n        \n#         for row in range(1, len(text2) + 1):\n#             for col in range(1, len(text1) + 1):\n#                 if text2[row - 1] == text1[col - 1]:\n#                     dp[row][col] = dp[row-1][col-1] + 1\n#                 else:\n#                     dp[row][col] = max(dp[row-1][col], dp[row][col-1])\n        \n#         return dp[-1][-1]\n        from functools import lru_cache\n\n        memo = {}\n        @lru_cache(maxsize=None)\n        def lcs(i, j):\n            if i == len(text1) or j == len(text2):\n                return 0\n            if (i, j) in memo:\n                return memo[(i, j)]\n            elif text1[i] ==  text2[j]:\n                r = 1 + lcs(i + 1, j + 1)\n            else:\n                r = max(lcs(i + 1, j), lcs(i, j + 1))\n                \n            memo[(i, j)] = r\n            return r\n        \n        return lcs(0, 0)", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n\n        memo = {}\n        def helper(i, j):\n            if i >= len(text1) or j >= len(text2):\n                return 0\n            if (i,j) in memo:\n                return memo[(i,j)]\n            if text1[i] == text2[j]:\n                memo[(i,j)] = 1 + helper(i+1, j+1)\n                return memo[(i,j)]\n            else:\n                memo[(i,j)] = max(helper(i, j+1), helper(i+1, j))\n                return memo[(i,j)]\n\n        return helper(0, 0)", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        memo = dict()\n        def solve(i, j):\n            if i == len(text1) or j == len(text2):\n                return 0\n            \n            if (i, j) in memo:\n                return memo[(i, j)]\n            \n            if text1[i] == text2[j]:\n                ans = 1 + solve(i+1, j+1)\n            else:\n                ans = max(solve(i+1, j), solve(i, j+1))\n                \n            memo[(i, j)] = ans\n            return ans\n        \n        return solve(0, 0)\n", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        import numpy as np\n        x=list(text1)\n        y=list(text2)\n        m=len(x)\n        n=len(y)\n        t=-1* np.ones((m+1,n+1))\n        for j in range(m+1):\n            t[j][0]=0\n        for i in range(n+1):\n            t[0][i]=0\n        print(t)\n        for i in range(1,n+1):\n            for j in range(1,m+1):\n                if x[j-1]==y[i-1]:\n                    t[j][i]=1+t[j-1][i-1]\n                else:\n                    t[j][i]=max(t[j-1][i],t[j][i-1])\n        return int(t[m][n])", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        def helper(i, j):\n            if (i,j) in self.h:\n                return self.h[i,j]\n            \n            if i == n1 or j==n2:\n                self.h[i,j] = 0\n                return 0\n\n            if text1[i]==text2[j]:\n                self.h[i,j] = helper(i+1, j+1)+1\n            else:\n                self.h[i,j] = max(helper(i+1, j), helper(i, j+1))\n            \n            return self.h[i,j]\n                \n        \n        n1 = len(text1)\n        n2 = len(text2)\n        \n        self.h = {}\n        \n        res = helper(0, 0)\n        \n        return res\n        \n#         n1 = len(text1)\n#         n2 = len(text2)\n#         s1 = '*'+text1\n#         s2 = '*'+text2\n        \n#         if n1==0 or n2==0:\n#             return 0\n        \n#         res = [[0 for _ in range(n2+1)] for _ in range(n1+1)]\n        \n#         for i in range(1, n1+1):\n#             for j in range(1, n2+1):\n#                 if s1[i] == s2[j]:\n#                     res[i][j] = res[i-1][j-1]+1\n#                 else:\n#                     res[i][j] = max(res[i][j-1], res[i-1][j])\n        \n#         return res[-1][-1]\n", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        cache = {}\n        def lcs(i, j):\n            if i == len(text1) or j == len(text2): return 0\n            if (i, j) in cache: return cache[(i, j)]\n            if text1[i] == text2[j]: \n                cache[(i, j)] = 1+lcs(i+1, j+1)\n                return cache[(i, j)]\n            cache[(i, j)] = max(lcs(i+1, j), lcs(i, j+1))\n            return cache[(i, j)]\n        return lcs(0,0)\n            \n", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        def helper(i1, i2):\n            if (i1, i2) in self.memo:\n                return self.memo[(i1, i2)]\n            \n            res = 0\n            if i1 == len(text1) or i2 == len(text2):\n                res = 0\n            elif text1[i1] == text2[i2]:\n                res = 1 + helper(i1 + 1, i2 + 1)\n            else:\n                res = max(helper(i1 + 1, i2), helper(i1, i2 + 1))\n            \n            self.memo[(i1, i2)] = res\n            return self.memo[(i1, i2)]\n        \n        self.memo = {}\n        return helper(0, 0)", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        def helper(i,j, dc):\n            if i<0 or j<0:\n                return 0\n            if (i,j) in dc:\n                return dc[(i,j)]\n            \n            if text1[i] == text2[j]:\n                dc[(i,j)] = helper(i-1,j-1,dc) + 1\n                return dc[(i,j)]\n            else:\n                dc[(i,j)] = max(helper(i-1,j,dc),\n                                helper(i,j-1,dc))\n                return dc[(i,j)]\n        return helper(len(text1)-1,len(text2)-1,{})\n            \n", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        self.memo = {}\n        self.t1 = text1\n        self.t2 = text2\n        \n        tup = (len(text1), len(text2))\n        return self.helper(tup)\n    \n    def helper(self, tup):\n        \n        if tup in self.memo:\n            return self.memo[tup]\n        elif tup[0] == 0 or tup[1] == 0:\n            return 0\n        elif self.t1[tup[0]-1] == self.t2[tup[1]-1]:\n            x = (tup[0]-1, tup[1]-1)\n            self.memo[tup] = 1+self.helper(x)\n        else:\n            a = (tup[0]-1, tup[1])\n            b = (tup[0], tup[1]-1)\n            \n            self.memo[tup] = max(\n                self.helper(a),\n                self.helper(b))\n            \n        return self.memo[tup]", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        if len(text2) < len(text1):\n            text1, text2 = text2, text1\n            \n        prev = [0] * (len(text1) + 1)\n        \n        # logic: if same, add 1, else max(try each without first)\n        # if row,col V == same, == prev diag + 1\n        # else: = max(row-1,col, row,col-1)\n        \n        for row in range(1, len(text2) + 1):\n            curr = [0] * (len(text1) + 1)\n            for col in range(1, len(text1) + 1):\n                if text2[row - 1] == text1[col - 1]:\n                    curr[col] = prev[col-1] + 1\n                else:\n                    curr[col] = max(prev[col], curr[col-1])\n            prev = curr\n        \n        return prev[-1]\n#         from functools import lru_cache\n\n#         memo = {}\n#         def lcs(i, j):\n#             if (i, j) in memo:\n#                 return memo[(i, j)]\n#             if i == len(text1) or j == len(text2):\n#                 r = 0\n#             elif text1[i] ==  text2[j]:\n#                 r = 1 + lcs(i + 1, j + 1)\n#             else:\n#                 r = max(lcs(i + 1, j), lcs(i, j + 1))\n                \n#             memo[(i, j)] = r\n#             return r\n        \n#         return lcs(0, 0)\n", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        cache = {}\n        def lcs(i, j):\n            if i == len(text1) or j == len(text2): return 0\n            if (i, j) in cache: return cache[(i, j)]\n            if text1[i] == text2[j]: return 1+lcs(i+1, j+1)\n            cache[(i, j)] = max(lcs(i+1, j), lcs(i, j+1))\n            return cache[(i, j)]\n        return lcs(0,0)\n            \n", "class Solution:\n    # def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n    #     matrix = [[None]*(len(text2)+1) for i in range(len(text1)+1)]\n    #     for j in range(len(text2)+1):\n    #         matrix[0][j] = 0\n    #     for i in range(len(text1)+1):\n    #         matrix[i][0] = 0\n    #     for i in range(1, len(text1)+1):\n    #         for j in range(1, len(text2)+1):\n    #             if text1[i-1] == text2[j-1]:\n    #                 matrix[i][j] = 1 + matrix[i-1][j-1]\n    #             else:\n    #                 matrix[i][j] = max(matrix[i-1][j], matrix[i][j-1])\n    #     return matrix[len(text1)][len(text2)]\n    \n    \n    \n    \n    \n    \n\n    \n    \n    \n\n\n    def longestCommonSubsequence(self, s1, s2):\n        def _longest_common_subsequence(s1, s2, cache):\n            p = (len(s1), len(s2))\n            if p in cache:\n                return cache[p]\n            elif len(s1) == 0 or len(s2) == 0:\n                return 0\n            elif s1[-1] == s2[-1]:\n                answer = 1 + _longest_common_subsequence(s1[:-1], s2[:-1], cache)\n                cache[p] = answer\n                return answer\n            else:\n                answer = max(_longest_common_subsequence(s1, s2[:-1], cache), _longest_common_subsequence(s1[:-1], s2, cache))\n                cache[p] = answer\n                return answer\n        return _longest_common_subsequence(s1, s2, {})", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        if len(text1) == 0 or len(text2) == 0:\n            return 0\n        \n        grid = [[[None, 0, None, None] for i in range(len(text1) + 1)] for i in range(len(text2) + 1)] \n        \n        for i in range(1, len(text2) + 1):\n            for j in range(1, len(text1) + 1):\n                if text1[j - 1] == text2[i - 1]:\n                    grid[i][j] = [text2[i - 1], grid[i - 1][j - 1][1] + 1, i - 1, j - 1]\n                else:\n                    if grid[i - 1][j][1] > grid[i][j - 1][1]:\n                        grid[i][j] = [None, grid[i - 1][j][1], i - 1, j]\n                    else:\n                        grid[i][j] = [None, grid[i][j - 1][1], i, j - 1]\n        return grid[-1][-1][1]\n", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        \n        def helper( memo, p1, p2 ):\n\n            if p1 >= len(text1) or p2 >= len(text2):\n                return 0\n            \n            if (p1, p2) in memo:\n                return memo[(p1, p2)]\n            \n            if text1[p1] == text2[p2]:\n                return 1 + helper( memo, p1+1, p2+1 )\n          \n            c1 = helper( memo, p1+1, p2 )\n            c2 = helper( memo, p1, p2+1 )\n\n            memo[(p1, p2)] = max(c1, c2) \n            return memo[(p1, p2)]\n\n        # need to memoize the p1, p2, and length\n        memo = {}\n        return helper( memo, 0, 0 )", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        \n        def helper( memo, p1, p2 ):\n\n            if p1 >= len(text1) or p2 >= len(text2):\n                return 0\n            \n            if (p1, p2) in memo:\n                return memo[(p1, p2)]\n            \n            if text1[p1] == text2[p2]:\n                return 1 + helper( memo, p1+1, p2+1 )\n\n            c1 = helper( memo, p1+1, p2 )\n            c2 = helper( memo, p1, p2+1 )\n\n            memo[(p1, p2)] = max( c1, c2 )\n            return memo[(p1, p2)]\n\n        # need to memoize the p1, p2, and length\n        memo = {}\n        return helper( memo, 0, 0 )", "class Solution:\n    # def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n    #     matrix = [[None]*(len(text2)+1) for i in range(len(text1)+1)]\n    #     for j in range(len(text2)+1):\n    #         matrix[0][j] = 0\n    #     for i in range(len(text1)+1):\n    #         matrix[i][0] = 0\n    #     for i in range(1, len(text1)+1):\n    #         for j in range(1, len(text2)+1):\n    #             if text1[i-1] == text2[j-1]:\n    #                 matrix[i][j] = 1 + matrix[i-1][j-1]\n    #             else:\n    #                 matrix[i][j] = max(matrix[i-1][j], matrix[i][j-1])\n    #     return matrix[len(text1)][len(text2)]\n    \n    \n    \n    \n    \n    \n\n    \n    \n    \n    def _longest_common_subsequence(self, s1, s2, cache):\n        p = (len(s1), len(s2))\n        if p in cache:\n            return cache[p]\n        elif len(s1) == 0 or len(s2) == 0:\n            return 0\n        elif s1[-1] == s2[-1]:\n            answer = 1 + self._longest_common_subsequence(s1[:-1], s2[:-1], cache)\n            cache[p] = answer\n            return answer\n        else:\n            answer = max(self._longest_common_subsequence(s1, s2[:-1], cache), self._longest_common_subsequence(s1[:-1], s2, cache))\n            cache[p] = answer\n            return answer\n\n    def longestCommonSubsequence(self, s1, s2):\n        return self._longest_common_subsequence(s1, s2, {})", "class Solution:\n    def longestCommonSubsequence1(self, s1: str, s2: str) -> int:\n        m = len(s1)\n        n = len(s2)\n        memo = [[-1 for _ in range(n + 1)] for _ in range(m + 1)]\n        return self.helper(s1, s2, 0, 0, memo)\n\n    def helper(self, s1, s2, i, j, memo):\n        if memo[i][j] < 0:\n            if i == len(s1) or j == len(s2):\n                memo[i][j] = 0\n            elif s1[i] == s2[j]:\n                memo[i][j] = 1 + self.helper(s1, s2, i + 1, j + 1, memo)\n            else:\n                memo[i][j] = max(\n                    self.helper(s1, s2, i + 1, j, memo),\n                    self.helper(s1, s2, i, j + 1, memo),\n                )\n        return memo[i][j]\n        \n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        def helper(i1, i2):\n            if (i1, i2) in self.memo:\n                return self.memo[(i1, i2)]\n            \n            res = 0\n            if i1 == len(text1) or i2 == len(text2):\n                res = 0\n            elif text1[i1] == text2[i2]:\n                res = 1 + helper(i1 + 1, i2 + 1)\n            else:\n                res = max(helper(i1 + 1, i2), helper(i1, i2 + 1))\n            \n            self.memo[(i1, i2)] = res\n            return self.memo[(i1, i2)]\n        \n        self.memo = {}\n        return helper(0, 0)", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        \n        @lru_cache(maxsize=None)\n        def helper(i1, i2):\n            if i1 == len(text1) or i2 == len(text2):\n                return 0\n            else:\n                if text1[i1] == text2[i2]:\n                    return helper(i1+1,i2+1) + 1\n                return max(helper(i1+1,i2), helper(i1,i2+1))\n        \n        return helper(0, 0)", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        m = len(text1)\n        n = len(text2)\n        dp = [[0] * (n+1) for _ in range(m+1)]\n        \n        for i in reversed(range(m)):\n            for j in reversed(range(n)):\n                if text1[i] == text2[j]:\n                    dp[i][j] = dp[i+1][j+1] + 1\n                else:\n                    dp[i][j] = max(dp[i+1][j], dp[i][j+1])\n                    \n        return dp[0][0]", "from collections import defaultdict\nclass Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        dp = defaultdict(lambda: -1)\n        \n        def helper(n, m):\n            if m < 0 or n < 0:\n                return 0\n            \n            if dp[(m, n)] == -1:\n                if text1[n] == text2[m]:\n                    length = 1 + helper(n-1, m-1)\n                else:\n                    length = max(helper(n-1, m), \n                                helper(n, m-1))\n                dp[(m, n)] = length\n            return dp[(m, n)]\n        return helper(len(text1)-1, len(text2)-1)", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        @lru_cache(None)\n        def lcs(s1,n,i,s2,m,j):\n            if i>=n or j>=m:\n                return 0\n            if s1[i]==s2[j]:\n                return 1 + lcs(s1,n,i+1,s2,m,j+1)\n            return max(lcs(s1,n,i+1,s2,m,j),lcs(s1,n,i,s2,m,j+1))\n        return lcs(text1,len(text1),0,text2,len(text2),0)\n", "class Solution:\n    import functools\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        longest = 0\n        memo = {}\n        # represents the lcs of the substring text1[:i] and text2[:j]\n        def calc_lcs(i, j):\n            if i < 0 or j < 0: return 0\n            if (i, j) in memo: return memo[(i, j)]\n            # if the char at the end of the substring text1[:i] == text2[:j], then\n            # we don't have to \\\"split out\\\" to search for the next common character, because we are already\n            # there!. so simply return 1 + calclcs(i - 1, j - 1)\n            if text1[i] == text2[j]: return 1 + calc_lcs(i - 1, j - 1)\n            # however, if the char at the end of the subtring text1[:i] DOESNT equal the char at the end \n            # of the substring text2[:j], then we have to \\\"split out\\\", to try to find the next common \n            # character. For example, say we had the strings \\\"abcd\\\", and \\\"ac\\\". Clearly, 'c' doesn't equal \n            # 'd'. So what do we do? We have to try to find either the next occurence of 'd' in the \n            # second string, or the next occurence of 'c' in the first string. What if both occur?\n            # well thats why we are taking the max! If both occur, it will result several \\\"lcs\\\"s being\n            # calculuated, and we want the largest one!\n            memo[(i, j)] = max(calc_lcs(i, j - 1), calc_lcs(i - 1, j))\n            return memo[(i, j)]\n        return calc_lcs(len(text1) - 1, len(text2) - 1)\n            \n", "from functools import lru_cache\n\nclass Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        if not text1 or not text2:\n            return 0\n        n, m = len(text1), len(text2)\n        \n        @lru_cache(maxsize=10000)\n        def lcs(i, j):\n            if i > n-1 or j > m-1:\n                return 0\n            if text1[i] == text2[j]:\n                return lcs(i+1, j+1) + 1\n            return max(lcs(i+1, j), lcs(i, j+1))\n            \n        return lcs(0, 0)\n                \n", "class Solution:\n    # \u5b9a\u4e49dp(i, j)\u662ftex1\u4e2d\u4ee5i\u5f00\u5934\u7684\u548ctext2\u4e2d\u4ee5j\u5f00\u5934\u7684\u6700\u957fcommon subsequence\n    # time O(mn) space O(mn)\n    # \u4e00\u822c\u8fd9\u79cd\u4e24\u4e2astring/array\u8ba9\u4f60dp\u7684\uff0c\u90fd\u662f\u5b9a\u4e49\u4ee5i/j\u4e3a\u8d77\u70b9/\u7ec8\u70b9\u7684\u4e2a\u6570/\u957f\u5ea6\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        if not text1 or not text2: return 0\n        \n        n, m = len(text1), len(text2)\n        M = {}\n        ret = 0\n        # \u548clongest palindromic subsequence\u7684dp\u72b6\u6001\u8f6c\u79fb\u4e00\u6837\n        def dp(i, j):\n            if i >= n or j >= m:\n                return 0\n            \n            if (i, j) in M: \n                return M[(i, j)]\n            \n            M[(i, j)] = 0\n            if text1[i] == text2[j]:\n                M[(i, j)] = 1+dp(i+1, j+1)\n            else:\n                M[(i, j)] = max(dp(i+1, j), dp(i, j+1))\n                \n            return M[(i, j)]\n        \n        return dp(0, 0)", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n    #     # return self.recursive(text1, text2, 0, 0)\n        dp = dict()\n        return self.top_down(dp, text1, text2, 0, 0)\n        # return self.bottom_up(text1, text2)\n    \n    def recursive(self, text1, text2, i, j):\n        if i >= len(text1) or j >= len(text2):\n            return 0\n        if text1[i] == text2[j]:\n            return 1+self.recursive(text1, text2, i+1, j+1)\n        a = self.recursive(text1, text2, i+1, j)\n        b = self.recursive(text1, text2, i, j+1)\n        return max(a, b)\n    \n    def top_down(self, dp, text1, text2, i, j):\n        if i >= len(text1) or j >= len(text2):\n            return 0\n        if text1[i] == text2[j]:\n            return 1+self.top_down(dp, text1, text2, i+1, j+1)\n        if (i, j) in dp:\n            return dp[(i, j)]\n        a = self.top_down(dp, text1, text2, i+1, j)\n        b = self.top_down(dp, text1, text2, i, j+1)\n        dp[(i, j)] = max(a, b)\n        return dp[(i, j)]\n\n    def bottom_up(self, text1, text2):\n        i, j = 0, 0\n        m, n = len(text1), len(text2)\n        dp = [[0]*(n+1) for _ in range(m+1)]\n        for i in range(1, m+1):\n            for j in range(1, n+1):\n                if text1[i-1] == text2[j-1]:\n                    dp[i][j] = 1+dp[i-1][j-1]\n                else:\n                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])\n        return dp[-1][-1]\n", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        mp = {}\n        def lcs(i, j):\n            if i>=len(text1) or j >=len(text2):\n                return 0\n            elif (i,j) in mp:\n                return mp[(i,j)]\n            else:\n                if text1[i] == text2[j]:\n                    mp[(i,j)] = 1+ lcs(i+1,j+1)\n                else:\n                    mp[(i,j)] = max(lcs(i+1,j), lcs(i,j+1))\n                return mp[(i,j)]\n        lcs(0,0)\n        return max(mp.values())", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        #hashh={}\n        def helper(text1,text2,i,j,hashh):\n            if i>=len(text1) or j>=len(text2):\n                return 0\n            leftElement=text1[i]\n            rightElement=text2[j]\n            if (i,j) in hashh:\n                return hashh[(i,j)]\n            if text1[i]==text2[j]:\n                hashh[(i,j)]=1+helper(text1,text2,i+1,j+1,hashh)\n            else:\n                temp1=helper(text1,text2,i+1,j,hashh)\n                temp2=helper(text1,text2,i,j+1,hashh)\n                hashh[(i,j)]=max(temp1,temp2)\n            return hashh[(i,j)]\n        return helper(text1,text2,0,0,{})", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        prev=[0 for j in range(len(text2)+1)]\n        curr=[0 for j in range(len(text2)+1)]\n        for i in range(len(text1)):\n            curr=[0 for j in range(len(text2)+1)]\n            for j in range(len(text2)):\n                \n                if text1[i]==text2[j]:\n                    curr[j+1]=prev[j]+1\n                    \n                else:\n                    curr[j+1]=max(prev[j+1],curr[j])\n                    \n            prev=curr\n                    \n        return prev[len(text2)]", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        if len(text1) == 0 or len(text2) == 0:\n            return 0\n\n        mem = [[-1 for _ in range(len(text2) + 1)] for _ in range(len(text1) + 1)]\n        return self.compute(mem, 0, 0, text1, text2)\n\n    def compute(self, mem, ptr1, ptr2, text1, text2):\n        # we are at the end\n        if ptr1 == len(text1) or ptr2 == len(text2):\n            return 0\n\n        if mem[ptr1][ptr2] != -1:\n            return mem[ptr1][ptr2]\n\n        if text1[ptr1] == text2[ptr2]:\n            ans = 1 + self.compute(mem, ptr1 + 1, ptr2 + 1, text1, text2)\n            mem[ptr1][ptr2] = ans\n            return ans\n        else:\n            ans = max(self.compute(mem, ptr1 + 1, ptr2, text1, text2), self.compute(mem, ptr1, ptr2 + 1, text1, text2))\n            mem[ptr1][ptr2] = ans\n            return ans\n", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        dp = [[0 for j in range(len(text2))] for i in range(len(text1))]\n        \n        dp[0][0] = int(text1[0] == text2[0])\n        # print(dp[0][0], text1[0], text2[0], text1[0] == text2[0], int(text1[0] == text2[0]), int(True))\n        \n        for i in range(1, len(text1)):\n            dp[i][0] = max(int(text1[i] == text2[0]), dp[i-1][0])\n            \n        for j in range(1, len(text2)):\n            dp[0][j] = max(int(text2[j] == text1[0]), dp[0][j-1])\n        \n        for i in range(1, len(text1)):\n            for j in range(1, len(text2)):\n                \n                if text1[i] == text2[j]:\n                    dp[i][j] = dp[i-1][j-1] + 1\n                else:\n                    dp[i][j] = max(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])\n        \n        print(dp)\n        return dp[-1][-1]", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        memo = {}\n        def helper(s1,s2,i1,i2):\n            if not s1 or not s2:\n                return 0\n            if (i1,i2) in memo:\n                return memo[(i1,i2)]\n            if s1[0] == s2[0]:\n                memo[(i1,i2)] = 1+helper(s1[1:],s2[1:],i1+1,i2+1)\n            else:\n                memo[(i1,i2)] =  max(helper(s1[1:],s2,i1+1,i2),helper(s1,s2[1:],i1,i2+1))\n            return memo[(i1,i2)]\n            \n        \n        \n        \n        \n        \n        \n        return helper(text1,text2,0,0)", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        \n        cache = [[-1 for _ in range(len(text2))] for _ in range(len(text1))]\n        \n        def lcs(text1, text2, i, j, cache):\n            \n            if i >= len(text1) or j >= len(text2):\n                return 0\n            if cache[i][j] != -1:\n                return cache[i][j]\n            elif text1[i] == text2[j]:\n                return 1 + lcs(text1, text2, i+1, j+1, cache)\n            else:\n                cache[i][j] = max(lcs(text1, text2, i, j+1, cache), lcs(text1, text2, i+1, j, cache))\n                return cache[i][j]\n            \n        \n        \n        a = lcs(text1, text2, 0, 0, cache)\n        # print(cache)\n        \n        return a", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        cache = {}\n        \n        def solve(t1,t2):\n            if t1 == len(text1) or t2 == len(text2):\n                return 0\n            \n            #check cache\n            if (t1,t2) in cache:\n                return cache[(t1,t2)]\n            \n            #case1\n            if text1[t1] == text2[t2]:\n                opt1 = solve(t1+1,t2+1)\n                cache[(t1+1,t2+1)] = opt1\n                return 1 + opt1\n            \n            #case2\n            else:\n                opt1 = solve(t1,t2+1)\n                opt2 = solve(t1+1,t2)\n                cache[(t1,t2+1)] = opt1\n                cache[(t1+1,t2)] = opt2\n                return max(opt1,opt2)\n                \n        return solve(0,0)", "from functools import lru_cache\nclass Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        t1,t2= text1,text2\n        @lru_cache(None)\n        def lcsh(m,n):\n            nonlocal t1,t2\n            if m==0 or n==0:\n                return 0\n            if t1[m-1]==t2[n-1]:\n                return 1 + lcsh(m-1,n-1)\n            else:\n                return max(lcsh(m-1,n),lcsh(m,n-1))\n        return lcsh(len(text1),len(text2))", "class Solution:\n    \n    def lcs(self, i, j):\n        if (i, j) not in self.memo:\n            if i == len(self.s) or j == len(self.p):\n                ans =  0\n            elif self.s[i] == self.p[j]:\n                ans = self.lcs(i+1, j+1) + 1\n            else:\n                ans = max(self.lcs(i+1, j), self.lcs(i, j+1))\n            self.memo[(i, j)] = ans\n        return self.memo[(i, j)]\n    \n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        self.s, self.p = text1, text2\n        self.memo = {}\n        return self.lcs(0, 0)", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        def helper(i1, i2):\n            if i1 == len(text1) or i2 == len(text2):\n                return 0\n            \n            if (i1, i2) in self.memo:\n                return self.memo[(i1, i2)]\n            \n            res = 0\n            if text1[i1] == text2[i2]:\n                res = 1 + helper(i1 + 1, i2 + 1)\n            else:\n                res = max(helper(i1 + 1, i2), helper(i1, i2 + 1))\n            \n            self.memo[(i1, i2)] = res\n            return self.memo[(i1, i2)]\n        \n        self.memo = {}\n        return helper(0, 0)", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        matrix = [0]*(len(text2)+1)\n        for i in range(1, len(text1)+1):\n            p = 0\n            for j in range(1, len(text2)+1):\n                if text1[i-1] == text2[j-1]:\n                    t = matrix[j]\n                    matrix[j] = 1 + p\n                    p = t\n                else:\n                    p = matrix[j]\n                    matrix[j] = max(matrix[j], matrix[j-1])\n        return matrix[len(text2)]", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        dp = [-1] * len(text1)\n        for i in range(len(dp)):\n            dp[i] = [-1] * len(text2)\n        \n        self.dp = dp\n        self.t1 = text1\n        self.t2 = text2\n        \n        return self.LCSHelper(len(text1)-1, len(text2)-1)\n    \n    def LCSHelper(self, i, j):\n        if i < 0 or i >= len(self.t1) or j < 0 or j >= len(self.t2):\n            return 0\n        \n        if self.dp[i][j] != -1:\n            return self.dp[i][j]\n        \n        if self.t1[i:i+1] == self.t2[j:j+1]:\n            self.dp[i][j] = 1 + self.LCSHelper(i-1, j-1)\n        else:\n            self.dp[i][j] = max(self.LCSHelper(i, j-1), self.LCSHelper(i-1, j))\n        \n        return self.dp[i][j]", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        hashh={}\n        def helper(text1,text2,i,j):\n            if i>=len(text1) or j>=len(text2):\n                return 0\n            leftElement=text1[i]\n            rightElement=text2[j]\n            if (i,j) in hashh:\n                return hashh[(i,j)]\n            if text1[i]==text2[j]:\n                hashh[(i,j)]=1+helper(text1,text2,i+1,j+1)\n                #return hashh[(i+1,j+1)]\n            else:\n                temp1=helper(text1,text2,i+1,j)\n                temp2=helper(text1,text2,i,j+1)\n                hashh[(i,j)]=max(temp1,temp2)\n            return hashh[(i,j)]\n        return helper(text1,text2,0,0)", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        def lcs(i, j):\n            \n            if i > len(text1)-1 or j > len(text2)-1:\n                return 0\n            if (i,j) in memo:\n                return memo[(i,j)]\n            if text1[i] == text2[j]:\n                memo[(i,j)] = 1 + lcs(i+1, j+1)\n            else:\n                memo[(i,j)] = max(lcs(i+1, j), lcs(i, j+1))\n                \n            return memo[(i,j)]\n            \n            \n        memo = {}\n        return lcs(0,0)", "from functools import lru_cache\nclass Solution:\n    def longestCommonSubsequence(self, text1, text2):\n        \n        @lru_cache(maxsize=None)\n        def memo_solve(p1, p2):\n            \n            # Base case: If either string is now empty, we can't match\n            # up anymore characters.\n            if p1 == len(text1) or p2 == len(text2):\n                return 0\n            \n            # Recursive case 1.\n            if text1[p1] == text2[p2]:\n                return 1 + memo_solve(p1 + 1, p2 + 1)\n            \n            # Recursive case 2.\n            else:\n                return max(memo_solve(p1, p2 + 1), memo_solve(p1 + 1, p2))\n            \n        return memo_solve(0, 0)", "# class Solution:\n#     def longestCommonSubsequence(self, s1: str, s2: str) -> int:\n        \n#         len_s1, len_s2 = len(s1), len(s2)\n        \n#         @lru_cache(None)\n#         def dp(i, j):\n#             if i == len_s1 or j == len_s2:\n#                 return 0\n            \n#             if s1[i] == s2[j]:\n#                 return 1 + dp(i+1, j+1)\n            \n#             return max(dp(i+1, j), dp(i, j+1))\n        \n#         return dp(0, 0)\n\nclass Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        memo = {}\n        \n        def lcs(i, j):\n            if (i, j) in memo:\n                return memo[(i, j)]\n            \n            if i == len(text1) or j == len(text2):\n                return 0\n            \n            move_both = None\n            if text1[i] == text2[j]:\n                move_both = 1 + lcs(i+1, j+1)\n                \n            move_i = lcs(i+1, j)\n            move_j = lcs(i, j+1)\n            memo[(i, j)] = max(move_i, move_j) if move_both is None else max([move_i, move_j, move_both])\n            return memo[(i, j)]\n        \n        return lcs(0, 0)", "def dp(s1, s2, i, j, mem):\n    if i >= len(s1) or j >= len(s2):\n        return 0\n    elif (i, j) in mem:\n        return mem[(i, j)]\n    \n    l = dp(s1, s2, i+1, j, mem)\n    r = dp(s1, s2, i, j+1, mem)\n    both = (1 + dp(s1, s2, i+1, j+1, mem)) if s1[i] == s2[j] else 0\n    res = max(r, l, both)\n    mem[(i, j)] = res\n    return res\n\nclass Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        return dp(text1, text2, 0, 0, {})", "class Solution:\n    def longestCommonSubsequence(self, s1: str, s2: str) -> int:\n        @lru_cache(maxsize = 10**18)\n        def LCS(s1 , s2 , n1 , n2):\n            if n1 == 0 or n2 == 0:return 0 \n            if s1[n1-1] == s2[n2 - 1]:return 1 + LCS(s1,s2,n1-1,n2-1)\n            else:return max(LCS(s1,s2,n1-1,n2),LCS(s1,s2,n1,n2-1))\n        return(LCS(s1,s2,len(s1),len(s2)))", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        t=[[-1 for j in range(len(text2)+1)]for i in range(len(text1)+1)]\n        for i in range(len(text1)+1):\n            for j in range(len(text2)+1):\n                t[0][j] = 0\n                t[i][0] = 0\n        res = self.LCS(text1,text2,len(text1), len(text2),t)\n        return res\n    def LCS(self,s1,s2,n,m,t):\n        if(t[n][m]!=-1):\n            return t[n][m]\n        \n        elif(s1[n-1]==s2[m-1]):\n            t[n][m] =  self.LCS(s1,s2,n-1,m-1,t) +1\n            return t[n][m]\n        \n        elif(s1[n-1]!=s2[m-1]):\n            t[n][m] = max(self.LCS(s1,s2,n-1,m,t), self.LCS(s1,s2,n,m-1,t))\n            return t[n][m]\n        \n", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        if len(text1) > len(text2):\n            text1, text2 = text2, text1\n        matrix = [0]*(len(text2)+1)\n        for i in range(1, len(text1)+1):\n            p = 0\n            for j in range(1, len(text2)+1):\n                if text1[i-1] == text2[j-1]:\n                    p, matrix[j] = matrix[j], 1 + p\n                else:\n                    p, matrix[j] = matrix[j], max(matrix[j], matrix[j-1])\n        return matrix[len(text2)]", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        memo = {}\n        self.dp(text1, text2, len(text1)-1, len(text2)-1, memo)\n        \n        return memo[(len(text1)-1, len(text2)-1)]\n    def dp(self, text1, text2, i, j, memo):\n        if i == -1 or j == -1:\n            return 0\n        if (i,j) in memo:\n            return memo[(i,j)]\n        \n        if text1[i] == text2[j]:\n            memo[(i,j)] = self.dp(text1, text2, i-1, j-1, memo) + 1\n            return memo[(i,j)]\n        else:\n            memo[(i,j)] =  max(self.dp(text1, text2, i-1, j, memo), self.dp(text1, text2, i, j-1, memo))\n            return memo[(i,j)]\n        return memo[(i,j)]\n        \n        \n", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        set1, set2 = set(text1), set(text2)\n        if not set1.intersection(set2):\n            return 0\n        \n        dp = [[0 for _ in range(len(text2)+1)] for _ in range(len(text1)+1)]\n        for i in range(1, len(text1)+1):\n            for j in range(1, len(text2)+1):\n                tmp = 0\n                if text1[i-1] == text2[j-1]:\n                    tmp = 1\n                dp[i][j] = max([dp[i-1][j], dp[i][j-1], dp[i-1][j-1]+tmp])\n                \n        return dp[-1][-1]", "class Solution:\n    def longestCommonSubsequence(self, t1: str, t2: str) -> int:\n        m, n = len(t1), len(t2)\n        dp = [[0]*(n+1) for _ in range(m+1)]\n        for i in range(1, m+1):\n            for j in range(1, n+1):\n                dp[i][j] = max(dp[i-1][j], dp[i][j-1])\n                dp[i][j] = max(dp[i][j], dp[i-1][j-1]+(1 if t1[i-1]==t2[j-1] else 0))\n        return dp[-1][-1]\n", "class Solution:\n    def __init__(self):\n        self.d = {}\n        \n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        def lcs(p1, p2):\n            if p1==len(text1) or p2==len(text2):\n                return 0\n            if (p1,p2) not in self.d:\n                if text1[p1]==text2[p2]:\n                    res = 1+lcs(p1+1,p2+1)\n                else:\n                    res = max( lcs(p1+1,p2), lcs(p1,p2+1) )\n                self.d[(p1, p2)] = res\n            return self.d[(p1, p2)]\n        return lcs(0,0)", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        \n        cache = [[None for j in range(len(text2))] for i in range(len(text1))]\n        self.memo(text1,text2,0,0,cache)\n        return cache[0][0]\n    def memo(self,word1,word2,i,j,cache):\n        if(i >= len(word1) or j >= len(word2)):\n            return 0\n        if(word1[i] == word2[j]):\n            if(cache[i][j] is None):\n                cache[i][j] = 1 + self.memo(word1,word2,i+1,j+1,cache)\n            return cache[i][j]\n        else:\n            if(cache[i][j] is None):\n                cache[i][j] = max(self.memo(word1,word2,i+1,j,cache), self.memo(word1,word2,i,j+1,cache))\n            return cache[i][j]\n        #TLE\n        '''\n        return self.recurse(text1,text2)\n    def recurse(self, word1, word2):\n        if(len(word1) == 0 or len(word2) == 0):\n            return 0\n        if(word1[0] == word2[0]):\n            return 1 + self.recurse(word1[1:], word2[1:])\n        else:\n            return max(self.recurse(word1[1:],word2),self.recurse(word1,word2[1:]))'''", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        dp = {}\n        def inner(i,j):\n            if i >= len(text1) or j >= len(text2):\n                return 0\n            \n            if dp.get((i,j)) == None:\n                if text1[i] == text2[j]:\n                    dp[(i,j)] = inner(i+1, j+1) + 1\n                else:\n                    dp[(i,j)] = max(inner(i+1, j),inner(i, j+1))\n            return dp[(i,j)]\n        return inner(0,0)        ", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        @lru_cache(maxsize=None)\n        def memo_solve(p1, p2):\n            \n            # Base case: If either string is now empty, we can't match\n            # up anymore characters.\n            if p1 == len(text1) or p2 == len(text2):\n                return 0\n            \n            # Recursive case 1.\n            if text1[p1] == text2[p2]:\n                return 1 + memo_solve(p1 + 1, p2 + 1)\n            \n            # Recursive case 2.\n            else:\n                return max(memo_solve(p1, p2 + 1), memo_solve(p1 + 1, p2))\n            \n        return memo_solve(0, 0)", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        m, n = len(text1), len(text2)\n        dp = [[0] * (n+1) for _ in range(m+1)]\n        max_len = 0\n        for i in range(1, m+1):\n            for j in range(1, n+1):\n                dp[i][j] = max(dp[i][j], dp[i-1][j], dp[i][j-1])\n                if text1[i-1] == text2[j-1]:\n                    dp[i][j] = max(dp[i][j], dp[i-1][j-1] + 1)\n                max_len = max(max_len, dp[i][j])\n        return max_len\n", "from functools import lru_cache\nclass Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        @lru_cache(maxsize=None)\n\n        \n        def helper(p1, p2)->int:\n            if p1==len(text1) or p2==len(text2):\n                return 0\n\n            option1 = dp[p1+1][p2] if visited[p1+1][p2]==1 else helper(p1+1, p2)\n            \n            first_occurrence = text2.find(text1[p1], p2)\n            if first_occurrence != -1:\n                option2 = dp[p1+1][first_occurrence+1] + 1 if visited[p1+1][first_occurrence+1]==1 else 1 + helper(p1+1, first_occurrence+1)\n            else:\n                option2 = 0\n            \n            visited[p1][p2] = 1\n            dp[p1][p2] = max(option1,option2)\n            \n            return dp[p1][p2]\n        \n        dp = [[0]*(len(text2)+1) for _ in range(len(text1)+1)]\n        visited = [[0]*(len(text2)+1) for _ in range(len(text1)+1)]\n                \n        return helper(0, 0)\n\n\n                    \n                \n                    \n        \n        \n", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        # return self.recursive(text1, text2, 0, 0)\n        dp = dict()\n        return self.top_down(dp, text1, text2, 0, 0)\n    \n    def recursive(self, text1, text2, i, j):\n        if i >= len(text1) or j >= len(text2):\n            return 0\n        if text1[i] == text2[j]:\n            return 1+self.recursive(text1, text2, i+1, j+1)\n        a = self.recursive(text1, text2, i+1, j)\n        b = self.recursive(text1, text2, i, j+1)\n        return max(a, b)\n    \n    def top_down(self, dp, text1, text2, i, j):\n        if i >= len(text1) or j >= len(text2):\n            return 0\n        if text1[i] == text2[j]:\n            return 1+self.top_down(dp, text1, text2, i+1, j+1)\n        if (i, j) in dp:\n            return dp[(i, j)]\n        a = self.top_down(dp, text1, text2, i+1, j)\n        b = self.top_down(dp, text1, text2, i, j+1)\n        dp[(i, j)] = max(a, b)\n        return max(a, b)", "from collections import defaultdict\nclass Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        dp = defaultdict(lambda: -1)\n        def helper(text1, n, text2, m):\n            if m == 0 or n == 0:\n                return 0\n            if dp[(m,n)] == -1:\n                if text1[-1] == text2[-1]:\n                    length = 1 + helper(text1[:-1], n-1, text2[:-1], m-1)\n                else:\n                    length = max(helper(text1[:-1], n-1, text2, m), \n                                helper(text1, n,text2[:-1], m-1))\n                dp[(m, n)] = length\n            return dp[(m, n)]\n        return helper(text1, len(text1), text2, len(text2))", "class Solution:\n    def longestCommonSubsequence(self, s1: str, s2: str) -> int:\n        return self.helper(s1, s2, 0, 0)\n    @lru_cache(None)\n    def helper(self, s1, s2, i, j):\n        if i == len(s1) or j == len(s2):\n            return 0\n        if s1[i] == s2[j]:\n            return 1 + self.helper(s1, s2, i + 1, j + 1)\n        else:\n            return max(self.helper(s1, s2, i+1, j), self.helper(s1, s2, i, j + 1))", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        \n        table={}\n        def helper(t1, t2, i,j, table):\n            if table.get((i,j)) != None:\n                return table[(i,j)]\n            \n            n = len(t1)\n            m = len(t2)\n            \n            if m <=j or n <= i:\n                return 0;\n            \n            \n            v = t1[i]\n            idx = t2.find(v, j)\n            if idx != -1:\n                r = max(helper(t1, t2, i+1, j, table), helper(t1, t2, i+1, idx+1, table)+1)\n                table[(i,j)] = r \n            else:\n                r = helper(t1, t2, i+1,j, table)\n                table[(i,j)] = r\n            return table[(i,j)]\n        \n        return helper(text1, text2, 0, 0, table)", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        map = {}\n        \n        def memo(p1, p2, map):\n            #print(concatChar)\n            if (p1, p2) in map:\n                return map[(p1, p2)]\n            else:\n                if p1 == len(text1) or p2 == len(text2):\n                    return 0\n                if text1[p1] == text2[p2]:\n                    map[(p1, p2)] = 1 + memo(p1+1, p2+1, map)\n                else:\n                    map[(p1, p2)] = max(memo(p1, p2+1, map), memo(p1+1, p2, map))\n                \n                # map[concatChar] = result\n                # print(map)\n                return map[(p1, p2)]\n        \n        return memo(0, 0, map)\n", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        lookup = [[None for x in range(len(text2))] for y in range(len(text1))]\n        def helper(s1, s2, pos1, pos2):\n            nonlocal lookup\n            if pos1 >= len(s1):\n                return 0\n            elif pos2 >= len(s2):\n                return 0\n            elif lookup[pos1][pos2] is not None:\n                return lookup[pos1][pos2]\n            else:\n                if s1[pos1] == s2[pos2]:\n                    lookup[pos1][pos2] = max(1 + helper(s1, s2, pos1 + 1, pos2 + 1),\n                              helper(s1, s2, pos1 + 1, pos2 + 1),\n                              helper(s1, s2, pos1, pos2 + 1),\n                              helper(s1, s2, pos1 + 1, pos2))\n                    return lookup[pos1][pos2]\n                else:\n                    lookup[pos1][pos2] = max(helper(s1, s2, pos1 + 1, pos2 + 1),\n                              helper(s1, s2, pos1, pos2 + 1),\n                              helper(s1, s2, pos1 + 1, pos2))\n                    return lookup[pos1][pos2]\n        return helper(text1, text2, 0, 0)\n", "class Solution:\n    def lcs_helper(self,s1,s2,lookup):\n        m, n = len(s1), len(s2)\n        lcs_look = lookup.get((m,n),-1)\n        if m==0 or n == 0:\n            return 0\n        if lcs_look != -1:\n            return lcs_look\n        if s1[-1] == s2[-1]:\n            lcs_look = self.lcs_helper(s1[:-1],s2[:-1],lookup)\n            lcs_look += 1\n            lookup[(m,n)] = lcs_look\n            return lcs_look\n        else:\n            lcs_look1 = self.lcs_helper(s1[:-1],s2,lookup)\n            lcs_look2 = self.lcs_helper(s1,s2[:-1],lookup)\n            lookup[(m,n)] = max(lcs_look1,lcs_look2)\n            return lookup[(m,n)]\n\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        m, n = len(text1), len(text2)\n        cache = {}\n        if m==0 or n == 0:\n            return 0\n        \n        return self.lcs_helper(text1,text2,cache)", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        dp = {}\n        l1 = len(text1)\n        l2 = len(text2)\n        if l1 == 0 or l2 == 0:\n            return 0\n        for i, c1 in enumerate(text1):\n            common = False\n            for j, c2 in enumerate(text2):\n                seq = 0\n                if c1 == c2:\n                    if (i-1, j-1) in dp:\n                        seq = max(seq, dp[(i-1, j-1)])\n                    seq += 1\n                else:\n                    if (i, j-1) in dp:\n                        seq = max(seq, dp[(i, j-1)])\n                    if (i-1, j) in dp:\n                        seq = max(seq, dp[(i-1, j)])\n                dp[(i, j)] = seq\n        return dp[(l1-1, l2-1)]", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        \n        # Make a grid of 0's with len(text2) + 1 columns\n        # and len(text1) + 1 rows\n        dp_grid = [[0] * (len(text2) + 1) for _ in range(len(text1) + 1)]\n        \n        # Iterate up each column, starting from the last one\n        for col in reversed(list(range(len(text2)))):\n            for row in reversed(list(range(len(text1)))):\n                if text2[col] == text1[row]:\n                    dp_grid[row][col] = 1 + dp_grid[row + 1][col + 1]\n                else:\n                    dp_grid[row][col] = max(dp_grid[row + 1][col], dp_grid[row][col + 1])\n        return dp_grid[0][0]\n", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        def memo(f):\n            dic = {}\n\n            def f_alt(*args):\n                if args not in dic:\n                    dic[args] = f(*args)\n                return dic[args]\n            return f_alt\n\n        @memo\n        def long(i, j):\n            if i == -1 or j == -1:\n                return 0\n            return max(long(i-1,j),long(i,j-1),long(i-1,j-1)+(text1[i] == text2[j]))\n\n        return long(len(text1)-1, len(text2)-1)", "import numpy as np\nclass Solution:\n    def longestCommonSubsequence(self, answer_text: str, source_text: str) -> int:\n        longest = 0\n        answer_text = ' ' + answer_text\n        source_text = ' ' + source_text\n        words_matrix = np.zeros((len(source_text), len(answer_text)))\n        for row in range(1, len(source_text)):\n            for col in range(1, len(answer_text)):\n                if source_text[row] == answer_text[col]:\n                    words_matrix[row][col] = words_matrix[row - 1][col - 1] + 1\n                else:\n                    words_matrix[row][col] = max(words_matrix[row - 1][col], words_matrix[row][col - 1])\n                longest = max(longest, words_matrix[row][col])\n        return int(longest)", "from functools import lru_cache \n\nclass Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        @lru_cache(None)\n        def helper(t1, t2):\n            if not t1 or not t2:\n                return 0\n            \n            if t1[-1] == t2[-1]: \n                return helper(t1[:-1], t2[:-1])  + 1\n                \n            else:\n                return max(helper(t1[:-1], t2), helper(t1, t2[:-1]))\n        \n        return helper(text1, text2)\n", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        cache = [[0]*len(text2) for _ in range(len(text1))]\n        return self.helper(text1, 0, text2, 0, cache)\n    \n    def helper(self, text1:str, i:int, text2:str, j:int, cache):\n        \n        if i==len(text1) or j==len(text2): return 0\n    \n        if cache[i][j]!= 0: return cache[i][j]\n        \n        if text1[i]==text2[j]:\n            cache[i][j] = 1+ self.helper(text1, i+1, text2, j+1, cache)\n        else:\n            cache[i][j] = max(self.helper(text1, i+1, text2, j, cache), self.helper(text1, i, text2, j+1, cache))\n            \n        return cache[i][j]", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        self.dp = {}\n        return self.recursiveLCS(text1, text2, len(text1)-1, len(text2)-1)\n        \n    def recursiveLCS(self, text1, text2, p1, p2):\n        if p1<0 or p2<0:\n            return 0\n        \n        if (p1, p2) in self.dp:\n            self.dp[(p1, p2)] = self.dp[(p1, p2)]\n            return self.dp[(p1, p2)]\n        \n        if text1[p1] == text2[p2]:\n            self.dp[(p1, p2)] = 1+self.recursiveLCS(text1, text2, p1-1, p2-1)\n        else:\n            self.dp[(p1, p2)] = max(\n                self.recursiveLCS(text1, text2, p1-1, p2),\n                self.recursiveLCS(text1, text2, p1, p2-1)\n            )\n        return self.dp[(p1, p2)]", "from typing import *\n\nclass Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        return longestCommonSubsequence_DP(text1, text2, 0, 0, dict())\n\ndef longestCommonSubsequence_DP(text1: str, text2: str, first_start_idx: int, second_start_idx: int, memo: Dict):\n    if (first_start_idx, second_start_idx) in memo:\n        return memo[(first_start_idx, second_start_idx)]\n\n    # base cases\n    if first_start_idx == len(text1) or second_start_idx == len(text2):\n        return 0\n\n    # recursive cases\n    first_cur_char = text1[first_start_idx]\n    second_cur_char = text2[second_start_idx]\n    ans_if_cur_same = -1\n    if first_cur_char == second_cur_char:\n        ans_if_cur_same = 1 + longestCommonSubsequence_DP(text1, text2, first_start_idx+1, second_start_idx+1, memo)\n\n    ans1_if_cur_diff = longestCommonSubsequence_DP(text1, text2, first_start_idx, second_start_idx+1, memo)\n    ans2_if_cur_diff = longestCommonSubsequence_DP(text1, text2, first_start_idx+1, second_start_idx, memo)\n\n    memo[(first_start_idx, second_start_idx)] = max(ans_if_cur_same if ans_if_cur_same != -1 else -math.inf,\n                                                    ans1_if_cur_diff,\n                                                    ans2_if_cur_diff)\n    return memo[(first_start_idx, second_start_idx)]", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        \n        # self.cache = [ [-1] * (len(text2) + 1) for _ in range(len(text1))]\n        # for row in self.cache:\n        #     row[-1] = 0\n        # self.cache.append([ 0 ] * (len(text2) + 1))\n        \n        self.cache = [ [-1] * len(text2) for _ in range(len(text1))]\n        \n        def findSubsequence(idx1, idx2):\n            if idx1 == len(text1) or idx2 == len(text2):\n                return 0\n            if self.cache[idx1][idx2] != -1:\n                return self.cache[idx1][idx2]\n            res = 0\n            if text1[idx1] == text2[idx2]:\n                res = 1 + findSubsequence(idx1 + 1, idx2 + 1)\n            else:\n                res = max(\n                    findSubsequence(idx1 + 1, idx2),\n                    findSubsequence(idx1, idx2 + 1)\n                )\n            self.cache[idx1][idx2] = res\n            return res\n        \n        return findSubsequence(0, 0)\n", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        #Bottom Up DP \n        if not text1 or not text2:\n            return 0\n        mem = [[0] * len(text2) for _ in range(len(text1))]\n        if text1[0] == text2[0]:\n            mem[0][0] = 1 \n        for i in range(1,len(text1)):\n            mem[i][0] = 1 if text1[i] == text2[0] else mem[i-1][0]\n        for i in range(1,len(text2)):\n            mem[0][i] = 1 if text2[i] == text1[0] else mem[0][i-1]\n        for i in range(1, len(text1)):\n            for j in range(1,len(text2)):\n                if text1[i] == text2[j]:\n                    mem[i][j] = max(mem[i-1][j-1]+1, mem[i][j-1], mem[i-1][j])\n                else:\n                    mem[i][j] = max(mem[i-1][j], mem[i][j-1])\n        return mem[-1][-1]\n                \n        \n        \n", "from functools import lru_cache\n\nclass Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        self.text1, self.text2 = text1, text2\n        return self.lcs(0, 0)\n        \n    @lru_cache(maxsize=None)\n    def lcs(self, from1, from2):\n        if from1 >= len(self.text1) or from2 >= len(self.text2): return 0 \n        if self.text1[from1] == self.text2[from2]:\n            return 1 + self.lcs(from1+1, from2+1)\n        else:\n            return max(self.lcs(from1, from2+1),\n                       self.lcs(from1+1, from2))\n", "from functools import lru_cache\nclass Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        self.text1 = text1\n        self.text2 = text2\n        return self.solve(len(text1), len(text2))\n    \n    @lru_cache(None)\n    def solve(self, m, n):\n        if not m or not n:\n            return 0\n        \n        if self.text1[m-1] == self.text2[n-1]:\n            return 1 + self.solve(m-1, n-1)\n        else:\n            return max(self.solve(m-1, n), self.solve(m, n-1))\n", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        \n        @lru_cache(maxsize=None)\n        \n        def LCS(t1,t2):\n\n            if(len(t1) == 0 or len(t2) == 0):\n                return 0\n            else:\n                if(t1[-1] == t2[-1]):\n                    return LCS(t1[0:-1],t2[0:-1]) + 1\n                else:\n                    return max(LCS(t1[0:-1],t2), LCS(t1,t2[0:-1]))     \n        \n        return LCS(text1,text2)", "import numpy as np\nclass Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        n = len(text1)\n        m = len(text2)\n        best = np.zeros((n+1,m+1))\n        ans = 0\n        for i in range(1,n+1):\n            for j in range(1,m+1):\n                \n                if text1[i-1]==text2[j-1]:\n                    best[i][j] = best[i-1][j-1] + 1\n                else:\n                    best[i][j] = max(best[i-1][j],best[i][j-1])\n                    \n                ans = max(ans,best[i][j])\n                \n        return int(ans)", "import numpy as np\n\nclass Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        l1 = len(text1)\n        l2 = len(text2)\n        if l1 == l2 and text1 == text2:\n            return l1\n        if l1 < l2:\n            text1, text2, l1, l2 = text2, text1, l2, l1\n        mat_ = np.zeros((l2+1, l1+1))\n        for j in range(1, l2+1):\n            for i in range(1, l1+1):\n                if text2[j-1] == text1[i-1]:\n                    mat_[j, i] = 1 + mat_[j-1, i-1]\n                else:\n                    mat_[j, i] = max(mat_[j, max(0, i-1)], mat_[max(0, j-1), i])\n        return int(mat_[-1][-1])\n", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        m = len(text1)\n        n = len(text2)\n        dp = []\n        for i in range(m+1):\n            dp.append([0] * (n+1))\n        for i in range(1, m+1):\n            text1_sub = text1[:i]\n            for j in range(1, n+1):\n                ch = text2[j-1]\n                options = [dp[i][j-1]]\n                last_idx = i - text1_sub[::-1].find(ch) - 1\n                if last_idx != i:\n                    options.append(1 + dp[last_idx][j-1])\n                dp[i][j] = max(options)\n        return dp[m][n]", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        record = [[0 for _ in range(len(text2))] for _ in range(len(text1))]\n        \n        def f(s1, s2, i, j):\n            if i>=len(s1) or j >=len(s2):\n                return 0\n            if record[i][j] > 0:\n                return record[i][j]\n            \n            if s1[i] == s2[j]:\n                #temp = max(1 + f(s1, s2, i+1, j+1), f(s1, s2, i, j+1), f(s1, s2, i+1, j))\n                temp = 1 + f(s1, s2, i+1, j+1)\n            else:\n                temp = max(f(s1, s2, i, j+1), f(s1, s2, i+1, j))\n            \n            record[i][j] = temp\n            return record[i][j]\n        \n        f(text1, text2, 0, 0)\n        return record[0][0]", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        dp=[[-1]*(len(text2)+1) for i in range(len(text1)+1)]\n        \n        def LCS(s1,s2,n,m,dp):\n            if n==0 or m==0:\n                return 0\n            if dp[n-1][m-1]!=-1:\n                return dp[n-1][m-1]\n            if s1[n-1]==s2[m-1]:\n                dp[n-1][m-1]=1+LCS(s1,s2,n-1,m-1,dp)\n                return dp[n-1][m-1]\n            else:\n                dp[n-1][m-1]=max(LCS(s1,s2,n-1,m,dp),LCS(s1,s2,n,m-1,dp))\n                return dp[n-1][m-1]\n            \n    \n    \n        \n        \n        return (LCS(text1,text2,len(text1),len(text2),dp))\n        \n", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        m = [[0] * len(text2) for _ in range(len(text1))]\n        \n        if text1[0] == text2[0]:\n            m[0][0] = 1\n        \n        for i in range(1, len(text1)):\n            m[i][0] = 1 if text1[i] == text2[0] else m[i-1][0]\n        for i in range(1, len(text2)):\n            m[0][i] = 1 if text2[i] == text1[0] else m[0][i-1]\n            \n        for i in range(1, len(text1)):\n            for j in range(1, len(text2)):\n                if text1[i] == text2[j]:\n                    m[i][j] = max(1 + m[i - 1][j - 1], m[i - 1][j], m[i][j - 1])\n                else:\n                    m[i][j] = max(m[i - 1][j], m[i][j - 1])\n        return m[-1][-1]", "from functools import lru_cache\n\nclass Solution:\n    \n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        \n#         @lru_cache(maxsize=None)\n#         def recurse(text1:str, text2:str) -> int:\n            \n#             if len(text1) == 0 or len(text2) == 0:\n#                 return 0\n            \n#             if text1[0] == text2[0]:\n#                 return 1+ recurse(text1[1:],text2[1:])\n#             else:\n#                 return max(recurse(text1,text2[1:]),recurse(text2,text1[1:]))\n        \n#         return recurse(text1,text2)\n        \n        @lru_cache(maxsize=None)\n        def recursion(text1:str, text2:str) -> int:\n            \n            if len(text1) == 0 or len(text2) == 0:\n                return 0\n            \n            if text1[0] == text2[0]:\n                return 1 + recursion(text1[1:], text2[1:])\n            \n            else:\n                return max(recursion(text1,text2[1:]), recursion(text1[1:], text2))\n        \n        return recursion(text1,text2)", "from functools import lru_cache\n\nclass Solution:\n    \n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        \n    \n        @lru_cache(maxsize=None)\n        def recursion(text1:str, text2:str) -> int:\n            \n            if len(text1) == 0 or len(text2) == 0:\n                return 0\n            \n            if text1[0] == text2[0]:\n                return 1 + recursion(text1[1:], text2[1:])\n            \n            else:\n                return max(recursion(text1,text2[1:]), recursion(text1[1:], text2))\n        \n        return recursion(text1,text2)", "from functools import lru_cache\n\nclass Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        @lru_cache(maxsize = None)\n        def memo_solve(p1, p2):\n            if len(text1) == p1 or len(text2) == p2:\n                return 0\n            \n            if text1[p1] == text2[p2]:\n                return 1 + memo_solve(p1 + 1, p2 + 1)\n            else:\n                return max(memo_solve(p1, p2 + 1), memo_solve(p1 + 1, p2))\n        return memo_solve(0, 0)\n        \n        \n#         @lru_cache(maxsize = None)\n#         def memo_solve(p1, p2):\n#             if len(text1) == p1 or len(text2) == p2:\n#                 return 0\n            \n#             option_1 = memo_solve(p1 + 1, p2)\n            \n#             first_occurence = text2.find(text1[p1], p2)\n#             option_2 = 0\n#             if first_occurence != -1:\n#                 option_2 = 1 + memo_solve(p1 + 1, first_occurence + 1)\n            \n#             return max(option_1, option_2)\n        \n#         return memo_solve(0, 0)\n", "from functools import lru_cache\n\nclass Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        n1 = len(text1)\n        n2 = len(text2)\n        \n        @lru_cache(None)\n        def dp(s1, s2):\n            if len(s1) == 0 or len(s2) == 0:\n                return 0\n            elif s1[0] == s2[0]:\n                return 1 + dp(s1[1:], s2[1:])\n            return max(dp(s1[1:], s2), dp(s1, s2[1:]))\n        \n        return dp(text1, text2)\n", "import numpy as np\nfrom functools import lru_cache\nclass Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        if len(text1) == 0 or len(text2) == 0:\n            return 0\n        \n        m = len(text1)\n        n = len(text2)\n        return self.dp(text1, text2, m-1, n-1)\n        \n#         A = np.zeros((m+1, n+1),int)\n        \n#         for i in range(1,m+1):\n#             for j in range(1,n+1):\n#                 if text1[i-1] == text2[j-1]:\n#                     A[i,j] = A[i-1,j-1] +1\n#                 else:\n#                     A[i,j] = max(A[i-1,j], A[i,j-1])\n#         return A[-1,-1]\n        \n    @lru_cache(maxsize=None)\n    def dp(self, text1, text2, i, j):\n        if i  < 0 or j < 0:\n            return 0\n        if text1[i] == text2[j]:\n            return self.dp(text1, text2, i-1, j-1) + 1\n        else:\n            return max(self.dp(text1, text2, i-1, j), self.dp(text1, text2, i, j-1))", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        @lru_cache(maxsize=None)\n        def memo_solve(p1, p2):\n            if p1==len(text1) or p2==len(text2):\n                return 0\n            \n            case1=memo_solve(p1+1, p2)\n            first = text2.find(text1[p1], p2)\n            case2=0\n            if first != -1:\n                case2 = 1 + memo_solve(p1+1, first +1)\n            \n            return max(case1, case2)\n        return memo_solve(0, 0)\n", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        \n        @lru_cache(maxsize=None)\n        def memo_solve(p1, p2):\n            \n            # Base case: If either string is now empty, we can't match\n            # up anymore characters.\n            if p1 == len(text1) or p2 == len(text2):\n                return 0\n            \n            # Option 1: We don't include text1[p1] in the solution.\n            option_1 = memo_solve(p1 + 1, p2)\n            \n            # Option 2: We include text1[p1] in the solution, as long as\n            # a match for it in text2 at or after p2 exists.\n            first_occurence = text2.find(text1[p1], p2)\n            option_2 = 0\n            if first_occurence != -1:\n                option_2 = 1 + memo_solve(p1 + 1, first_occurence + 1)\n            \n            # Return the best option.\n            return max(option_1, option_2)\n                \n        return memo_solve(0, 0)", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        memo = [[0]*(len(text2)+1) for i in range(len(text1)+1)]\n        s1=text1\n        s2=text2\n        def helper(i1,i2):\n            if memo[i1][i2]:\n                return memo[i1][i2]\n            if i1 == len(s1) or i2 == len(s2):\n                return 0\n            if s1[i1] == s2[i2]:\n                memo[i1][i2] = 1+helper(i1+1,i2+1)\n                \n            else:\n                memo[i1][i2] =  max(helper(i1+1,i2),helper(i1,i2+1))\n            return memo[i1][i2]\n            \n        \n        \n        \n        \n        \n        \n        return helper(0,0)", "from functools import lru_cache\n\n\nclass Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        '''\n        base case:\n        text1 = c1, text2 = c2\n        if c1 == c2 return 1, if c1 != c2 return 0\n        text1 = sub1 + c1 -> c1 is the last char\n        text2 = sub2 + c2\n        \n        DP(text1, text2) = max(DP(text1, sub2), DP(sub1, text2), DP(sub1, sub2))\n                           or DP(sub1, sub2) + 1 if c1 == c2\n        '''\n        if len(text1) == 0 or len(text2) == 0:\n            return 0\n        \n        @lru_cache(None)\n        def lcs_of_sub(s1, s2):\n            if not s1 or not s2:\n                return 0\n            c1, c2 = s1[-1], s2[-1]\n            sub1, sub2 = s1[:-1], s2[:-1]\n            # print(sub1, c1, sub2, c2)\n            if c1 == c2:\n                return lcs_of_sub(sub1, sub2) + 1\n            return max(\n                lcs_of_sub(sub1, sub2), lcs_of_sub(sub1, s2), lcs_of_sub(s1, sub2)\n            )\n        \n        return lcs_of_sub(text1, text2)", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        memo={}\n        def LCS(s1,s2, i1, i2):\n            if i1>len(s1)-1 or i2>len(s2)-1: return 0\n            if (i1,i2) in memo: return memo[(i1,i2)]\n            if s1[i1]==s2[i2]:\n                memo[(i1,i2)]=1+ LCS(s1,s2,i1+1,i2+1)\n                return memo[(i1,i2)]\n            s1_next=LCS(s1,s2,i1+1,i2)\n            s2_next=LCS(s1,s2,i1,i2+1)\n            memo[(i1,i2)]= max(s1_next,s2_next)\n            return memo[(i1,i2)]\n        \n        return LCS(text1,text2,0,0)\n                    \n                \n    \n    \n    \n    \n", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        \n        memo = [[None for i in range(len(text2)+1)] for _ in range(len(text1)+1)]\n        def rec(i, j):\n            if i == len(text1) or j == len(text2):\n                return 0\n            \n            if text1[i] == text2[j]:\n                if not memo[i+1][j+1]:\n                    memo[i+1][j+1] = rec(i+1, j+1)\n                return 1 + memo[i+1][j+1]\n            else:\n                if not memo[i][j+1]:\n                    memo[i][j+1] = rec(i, j+1)\n                if not memo[i+1][j]:\n                    memo[i+1][j] = rec(i+1, j)\n                return max(memo[i][j+1], memo[i+1][j])\n            \n        return rec(0, 0)", "class Solution:\n    def __init__(self):\n        self.cached = {}\n        \n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        if len(text1) == 0 or len(text2) == 0:\n            return 0\n        \n        \n        if (len(text1), len(text2)) in self.cached:\n            return self.cached[(len(text1), len(text2))]\n        \n        if text1[-1] == text2[-1]:\n            r = self.longestCommonSubsequence(text1[:-1], text2[:-1]) + 1\n        else:\n            r = max(\n                self.longestCommonSubsequence(text1, text2[:-1]),\n                self.longestCommonSubsequence(text1[:-1], text2)\n            )\n        \n        self.cached[(len(text1), len(text2))] = r\n        \n        return r\n", "class Solution:\n    @lru_cache(maxsize = None)\n    def longest(self, p1, p2):\n        if p1 == len(self.t1) or p2 == len(self.t2):\n            return 0\n        \n        if self.t1[p1] == self.t2[p2]:\n            return 1 + self.longest(p1 + 1, p2 + 1)\n        \n        return max(self.longest(p1 + 1, p2), self.longest(p1, p2 + 1))\n    \n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        self.t1 = text1\n        self.t2 = text2\n        return self.longest(0, 0)", "class Solution:\n    def longestCommonSubsequence(self, str1: str, str2: str) -> int:\n    \n        cache = [ [-1]*len(str2) for _ in str1]\n\n        \n        def checkPosition(i1, i2):\n            \n            if i1 == len(str1) or i2 == len(str2):\n                return 0\n            \n            #hashing\n            if cache[i1][i2] != -1:\n                return cache[i1][i2]\n\n            # the characters match, so we can keep both\n            if str1[i1] == str2[i2]:\n                keep = 1 + checkPosition(i1+1, i2+1)\n\n            else: \n                keep = -1\n\n            skip1 = checkPosition(i1+1, i2)\n            skip2 = checkPosition(i1, i2+1)\n            \n            best = max([keep, skip1, skip2])\n            cache[i1][i2] = best\n            return best\n\n        return checkPosition(0,0)\n    \n    \n\n", "class Solution:\n    \n    def _longest_common_subsequence(self, s1, s2, cache):\n        if (s1, s2) in cache:\n            return cache[(s1, s2)]\n        elif len(s1) == 0 or len(s2) == 0:\n            cache[(s1, s2)] = 0\n            return 0\n        elif s1[-1] == s2[-1]:\n            answer = 1 + self._longest_common_subsequence(s1[:-1], s2[:-1], cache)\n            cache[(s1, s2)] = answer\n            return answer\n        else:\n            answer = max(self._longest_common_subsequence(s1, s2[:-1], cache), self._longest_common_subsequence(s1[:-1], s2, cache))\n            cache[(s1, s2)] = answer\n            return answer\n    \n    def longestCommonSubsequence(self, s1: str, s2: str) -> int:\n        return self._longest_common_subsequence(s1, s2, {})", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        def lcs(i,j):\n            if i==len(text1) or j==len(text2):\n                return 0\n            if tuple([i,j]) in dp:\n                return dp[tuple([i,j])]\n            if text1[i]==text2[j]:\n                dp[tuple([i,j])]=1+lcs(i+1,j+1)\n                return dp[tuple([i,j])]\n            dp[tuple([i,j])]=max(lcs(i+1,j),lcs(i,j+1))\n            return dp[tuple([i,j])]\n        dp={}\n        # text1+=\\\"0\\\"\n        # text2+=\\\"0\\\"\n        return lcs(0,0)", "class Solution:\n    def longestCommonSubsequence(self, s1: str, s2: str) -> int:\n        def rec(s1, s2, i, j, lcs):\n            if i == len(s1) or j == len(s2):\n                return 0\n            if (i, j) in lcs:\n                return lcs[(i, j)]\n            else:\n                if s1[i] == s2[j]:\n                    lcs[(i, j)] = 1 + rec(s1, s2, i + 1, j + 1, lcs)\n                else:\n                    l = rec(s1, s2, i + 1, j, lcs)\n                    r = rec(s1, s2, i, j + 1, lcs)\n                    lcs[(i, j)] = max(l, r)\n                return lcs[(i, j)]\n        return rec(s1, s2, 0, 0, {})", "class Solution:\n    # def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n    #     matrix = [[None]*(len(text2)+1) for i in range(len(text1)+1)]\n    #     for j in range(len(text2)+1):\n    #         matrix[0][j] = 0\n    #     for i in range(len(text1)+1):\n    #         matrix[i][0] = 0\n    #     for i in range(1, len(text1)+1):\n    #         for j in range(1, len(text2)+1):\n    #             if text1[i-1] == text2[j-1]:\n    #                 matrix[i][j] = 1 + matrix[i-1][j-1]\n    #             else:\n    #                 matrix[i][j] = max(matrix[i-1][j], matrix[i][j-1])\n    #     return matrix[len(text1)][len(text2)]\n    \n    \n    def _longest_common_subsequence(self, s1, s2, cache):\n        if (s1, s2) in cache:\n            return cache[(s1, s2)]\n        elif len(s1) == 0 or len(s2) == 0:\n            return 0\n        elif s1[-1] == s2[-1]:\n            answer = 1 + self._longest_common_subsequence(s1[:-1], s2[:-1], cache)\n            cache[(s1, s2)] = answer\n            return answer\n        else:\n            answer = max(self._longest_common_subsequence(s1, s2[:-1], cache), self._longest_common_subsequence(s1[:-1], s2, cache))\n            cache[(s1, s2)] = answer\n            return answer\n\n    def longestCommonSubsequence(self, s1, s2):\n        return self._longest_common_subsequence(s1, s2, {})", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        memo = [[ -1 for i in range(len(text2))] for i in range (len(text1))]\n        \n        def memoSolve(i, j) :\n            if i == len(text1) or j == len(text2):\n                return 0\n            \n            if memo[i][j] >= 0:\n                return memo[i][j]\n            \n            includeHere = 0\n            if (text1[i] == text2[j]):\n                includeHere = 1 + memoSolve(i + 1, j + 1)\n            includeLater = memoSolve(i, j+1)\n            included = max(includeHere, includeLater)\n            noTake = max(memoSolve(i + 1, j), memoSolve(i+1, j+1))\n            \n            memo[i][j] = max(included, noTake)\n            return memo[i][j]\n            \n        return memoSolve(0,0)", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        \n        @lru_cache(maxsize=None)\n        def memo_solve(p1, p2):\n            \n            # Base case: If either string is now empty, we can't match\n            # up anymore characters.\n            if p1 == len(text1) or p2 == len(text2):\n                return 0\n            \n            # Option 1: We don't include text1[p1] in the solution.\n            option_1 = memo_solve(p1 + 1, p2)\n            \n            # Option 2: We include text1[p1] in the solution, as long as\n            # a match for it in text2 at or after p2 exists.\n            first_occurence = text2.find(text1[p1], p2)\n            option_2 = 0\n            if first_occurence != -1:\n                option_2 = 1 + memo_solve(p1 + 1, first_occurence + 1)\n            \n            # Return the best option.\n            return max(option_1, option_2)\n                \n        return memo_solve(0, 0)    ", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        # dp[i][j] = dp[i-1][j-1] + 1 if text1[i] == text2[j]\n        # else max(dp[i-1][j], dp[i][j-1])\n        m, n = len(text1), len(text2)\n        dp = [[0]*(n+1) for _ in range(m+1)]\n        for i in range(1, m+1):\n            for j in range(1, n+1):\n                if text1[i-1] == text2[j-1]:\n                    dp[i][j] = dp[i-1][j-1] + 1\n                else:\n                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])\n        return dp[-1][-1]", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        memo = [[0]*len(text2) for i in range(len(text1))]\n        def helper(s1,s2,i1,i2):\n            if not s1 or not s2:\n                return 0\n            if memo[i1][i2]:\n                return memo[i1][i2]\n            if s1[0] == s2[0]:\n                memo[i1][i2] = 1+helper(s1[1:],s2[1:],i1+1,i2+1)\n                \n            else:\n                memo[i1][i2] =  max(helper(s1[1:],s2,i1+1,i2),helper(s1,s2[1:],i1,i2+1))\n            return memo[i1][i2]\n            \n        \n        \n        \n        \n        \n        \n        return helper(text1,text2,0,0)", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        n, m = len(text1), len(text2)\n        dp = [[0] * (m + 1) for _ in range(n + 1)]\n        for row in range(1, n + 1):\n            for col in range(1, m + 1):\n                if text1[row - 1] == text2[col - 1]:\n                    dp[row][col] = 1 + dp[row - 1][col - 1]\n                else:\n                    dp[row][col] = max(dp[row - 1][col], dp[row][col - 1])\n        return dp[n][m]\n    \n    def longestCommonSubsequence1(self, text1: str, text2: str) -> int:\n        def helper(i1, i2):\n            if (i1, i2) in self.memo:\n                return self.memo[(i1, i2)]\n            \n            res = 0\n            if i1 == len(text1) or i2 == len(text2):\n                res = 0\n            elif text1[i1] == text2[i2]:\n                res = 1 + helper(i1 + 1, i2 + 1)\n            else:\n                res = max(helper(i1 + 1, i2), helper(i1, i2 + 1))\n            \n            self.memo[(i1, i2)] = res\n            return self.memo[(i1, i2)]\n        \n        self.memo = {}\n        return helper(0, 0)", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        n,m=len(text1),len(text2)\n        dp=[[0]*(m+1) for _ in range(n+1)]\n        for i in range(n):\n            for j in range(m):\n                if text1[i]==text2[j]:\n                    dp[i+1][j+1]=dp[i][j]+1\n                else:\n                    dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j])\n        return dp[-1][-1]", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        \n        \n        dp=[[0]*(len(text2)+1) for _ in range(len(text1)+1)]\n        \n        for i in range(1,len(dp)):\n            for j in range(1,len(dp[0])):\n                \n                if text1[i-1]==text2[j-1]:\n                    dp[i][j]=dp[i-1][j-1]+1\n                else:\n                    dp[i][j]=max(dp[i-1][j],dp[i][j-1])\n                \n                \n        return dp[-1][-1]\n", "class Solution:\n    def helper(self, text1, text2, index1, index2, match):\n        if index1 == len(text1) or index2 == len(text2):\n            return match\n        s1 = 0\n        s2 = 0\n        s3 = 0\n        # case - match\n        if text1[index1] == text2[index2]:\n            s1 = self.helper(text1, text2, index1+1, index2+1, match+1)\n        else:\n            # case - did not match\n            s2 = self.helper(text1, text2, index1, index2+1, match)\n            s3 = self.helper(text1, text2, index1+1, index2, match)\n            \n        return max(s1, s2, s3)\n        \n    \n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        \n        if not text1 or not text2:\n            return 0\n        \n        dp = [[0 for i in range(len(text1)+1)] for j in range(len(text2)+1)]\n        \n        for i in range(1, len(dp)):\n            for j in range(1, len(dp[0])):\n                \n                if text1[j-1] == text2[i-1]:\n                    dp[i][j] = 1 + dp[i-1][j-1]\n                else:\n                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])\n                    \n        return dp[len(text2)][len(text1)]\n", "class Solution:\n    def longestCommonSubsequence(self, stringA: str, stringB: str) -> int:\n        lengthA = len(stringA)\n        lengthB = len(stringB)\n        dp = [[ 0 for j in range(lengthB + 1)] for i in range(lengthA + 1)]\n        for i in range(1, lengthA + 1):\n            for j in range(1, lengthB + 1):\n                if stringA[i - 1] == stringB[j - 1]:\n                    dp[i][j] = dp[i - 1][j - 1] + 1\n                else:\n                    dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])\n        return dp[lengthA][lengthB]\n", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        \n        len1 = len(text1)\n        len2 = len(text2)\n        \n        dp = [[0 for _ in range(len2+1)] for _ in range(len1+1)]\n        \n        for i in range(len1):\n            for j in range(len2):\n                if text1[i] == text2[j]:\n                    dp[i+1][j+1] = dp[i][j]+1\n                else:\n                    dp[i+1][j+1] =  max(dp[i][j+1],dp[i+1][j])\n                    \n        \n        return dp[len1][len2]\n", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        # use dynamic programming\n        \n        # initialize table to store sub solutions\n        # row (i) = index of text1 + 0 for initial row\n        # column (j) = index of text2 + 0 for initial row\n        # cell = max length of subsequence for text1[1:i] text2[1:j]\n        t = [[0 for _ in range(len(text2)+1)] for _ in range(len(text1)+1)]\n        \n        \n        # loop through each element\n        for i in range(1, len(text1)+1):\n            for j in range(1, len(text2)+1):\n                # if text is the same, diagonal cell + 1\n                if text1[i-1] == text2[j-1]:\n                    t[i][j] = t[i-1][j-1] + 1\n                # else, max of above (not considering last of text 1) or left\n                else:\n                    t[i][j] = max(t[i-1][j], t[i][j-1])\n        \n        # return right bottom of table\n        return t[len(text1)][len(text2)]        \n", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        if not text1 or not text2:\n            return 0\n        m, n = len(text1), len(text2)\n        dp = [[0 for _ in range(n+1)] for _ in range(m+1)]\n        for i in range(1, m+1):\n            for j in range(1, n+1):\n                if text1[i-1] == text2[j-1]:\n                    dp[i][j] = dp[i-1][j-1] + 1\n                else:\n                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])\n        return dp[m][n]\n\n", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        # dp\n        if not text1 or not text2:\n            return 0\n        m, n = len(text1), len(text2)\n        dp = [[0 for _ in range(n+1)] for _ in range(m+1)]\n        for i in range(1, m+1):\n            for j in range(1, n+1):\n                if text1[i-1] == text2[j-1]:\n                    dp[i][j] = dp[i-1][j-1] + 1\n                else:\n                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])\n        return dp[m][n]\n", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        \n        \n        row = len(text1) + 1\n        col = len(text2) + 1\n        \n        \n        dp = [[0 for _ in range(col)] for _ in range(row)]\n        \n        for i in range(1,row):\n            for j in range(1,col):\n                \n                if(text1[i-1] == text2[j-1]):\n                    dp[i][j] = dp[i-1][j-1] + 1\n                else:\n                    dp[i][j] = max(dp[i-1][j],dp[i][j-1])\n                    \n        \n        return dp[-1][-1]\n", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        ans = 0\n        dp = [[0 for _ in range(len(text1)+1)] for _ in range(len(text2)+1)]\n        \n        for i in range(1, len(text2)+1):\n            for j in range(1, len(text1)+1):\n                if text2[i-1] == text1[j-1]:\n                    dp[i][j] = dp[i-1][j-1]+1\n                else:\n                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])\n            ans = max(ans, dp[i][j])\n        return ans\n      \n", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        dp = [[0 for _ in range(len(text2) + 1)] for _ in range(len(text1) + 1)]\n        \n        for i in range(1, len(text1) + 1):\n            for j in range(1, len(text2) + 1):\n                if text1[i - 1] == text2[j - 1]:\n                    dp[i][j] = dp[i - 1][j - 1] + 1\n                else:\n                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])\n        return dp[-1][-1]\n", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        L1=len(text1)\n        L2=len(text2)\n        A=[ [0]*(L2+1) for i in range(L1+1)]\n\n        ##print(A)\n        Max=0\n        ##print(L1,L2)\n        for i in range(L1,-1,-1):\n                for j in range(L2,-1,-1):\n                    if i<L1 and j<L2:\n                        ##print(i,j)\n                        if text1[i]==text2[j]:\n                                A[i][j]= A[i+1][j+1]+1\n                        else: A[i][j]=max(A[i][j+1],A[i+1][j])\n                    if Max<A[i][j]: Max=A[i][j]\n\n\n        ##print(A[2][3])\n        return A[i][j]\n    \n        \n        \n        \n", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        s1=text1\n        s2=text2\n        if len(s1)==0 or len(s2)==0:\n            return 0\n        rows,cols=len(s1)+1,len(s2)+1\n        arr = [[0 for i in range(cols)] for j in range(rows)] \n        for i in range(len(s1)):\n            for j in range(len(s2)):\n                if s1[i]==s2[j]:\n                    arr[i][j]=arr[i-1][j-1]+1\n                if s1[i]!=s2[j]:\n                    arr[i][j]=max(arr[i-1][j],arr[i][j-1])\n        return (arr[rows-2][cols-2])\n", "class Solution:\n    def longestCommonSubsequence(self, A: str, B: str) -> int:\n        m,n = len(A), len(B)\n        dp = [[0]*(n+1) for i in range(m+1)]\n        for i in range(m+1):\n            for j in range(n+1):\n                if i==0 or j==0:\n                    dp[i][j] =0\n                elif A[i-1] == B[j-1]:\n                    dp[i][j] = 1+dp[i-1][j-1]\n                else:\n                    dp[i][j] = max(dp[i-1][j], dp[i][j-1] )\n        return dp[m][n]\n", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        dp = [0]*(len(text2)+1)\n        for i in range(1, len(text1)+1):\n            prev = dp[0]\n            for j in range(1, len(text2)+1):\n                last = dp[j]\n                if text1[i-1]==text2[j-1]:\n                    dp[j] = prev+1\n                if last>prev:\n                    prev = last\n        return max(dp)", "class Solution:\n    def longestCommonSubsequence(self, s1: str, s2: str) -> int:\n        \n        #\u6ce8\u610f\u8fd9\u91cc\u4e0d\u8981\u5199\u6210\u30100 * \uff08len....\uff09\u3011\n        dp_grid = [[0] * (len(s1) + 1) for _ in range(len(s2) + 1)]\n        \n        for r in range(len(s2) + 1):\n            for c in range(len(s1) + 1):\n                \n                if r == 0 or c == 0: \n                    dp_grid[r][c] = 0\n                    \n                #\u6ce8\u610f\u8fd9\u91cc\u7684s2\u548cs1\u662fstring,\u522b\u641e\u9519\u5199\u6210s2[r-1][c-1]\u4e86\n                elif s2[r-1] == s1[c-1]:\n                    dp_grid[r][c] = dp_grid[r-1][c-1] + 1\n                \n                else:\n                    dp_grid[r][c] = max(dp_grid[r-1][c], dp_grid[r][c-1])\n                \n        return dp_grid[-1][-1]\n    \n                    \n", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        \n        if not text1 or not text2: return 0\n        dp = [[0 for i in range(len(text1))] for j in range(len(text2))]\n        for i in range(len(text2)):\n            for j in range(len(text1)):\n                if i == 0 and j == 0:\n                    dp[i][j] = 1 if text1[j] == text2[i] else 0\n                elif i == 0:\n                    if dp[i][j-1] == 0 and text1[j] == text2[i]: dp[i][j] = 1\n                    else: dp[i][j] = dp[i][j-1]\n                elif j == 0:\n                    dp[i][j] = 1 if dp[i-1][j] == 1 or text1[j] == text2[i] else 0\n                elif text1[j] == text2[i]:\n                    dp[i][j] = 1 + dp[i-1][j-1]\n                else:\n                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])\n        return dp[-1][-1]", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:    \n        def lcsTab(s1,s2,m,n):\n            dp = [[0 for i in range(n+1)] for j in range(m+1)]\n            \n            for i in range(m+1):\n                for j in range(n+1):\n                    if(i==0 or j==0):\n                        dp[i][j] = 0\n                    elif(s1[i-1] == s2[j-1]):\n                        dp[i][j] = 1+dp[i-1][j-1]\n                    else:\n                        dp[i][j] = max(dp[i-1][j],dp[i][j-1])\n            \n            return dp[m][n]\n            \n        m = len(text1)\n        n = len(text2)\n        \n        return lcsTab(text1,text2,m,n)\n        \n", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        n=len(text1)\n        m=len(text2)\n        dp=[[0 for i in range(m+1)] for i in range(n+1)]\n        \n        for i in range(1,n+1):\n            for j in range(1,m+1):\n                \n                if text1[i-1] == text2[j-1]:\n                    dp[i][j]=1+dp[i-1][j-1]\n                    \n                else:\n                    dp[i][j]=max(dp[i-1][j],dp[i][j-1])\n        print(dp)            \n        return dp[n][m]           \n", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        \n        dynamic_array = [[0 for c in range(len(text2)+1)] for ch in range(len(text1)+1)]\n        \n        \n        for i in range(len(text1)+1):\n            for j in range(len(text2)+1):\n                \n                if i == 0 or j == 0:\n                    dynamic_array[i][j] = 0\n                elif text1[i-1] == text2[j-1]:\n                    dynamic_array[i][j] = 1 + dynamic_array[i-1][j-1]\n                else:\n                    dynamic_array[i][j] = max(dynamic_array[i-1][j],dynamic_array[i][j-1])\n        \n        return dynamic_array[len(text1)][len(text2)]\n        \n        \n", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        l1 = len(text1)\n        l2 = len(text2)\n        dp = [[0 for c in range(l2+1)] for r in range(l1+1)]\n        \n        for i in range(l1):\n            for j in range(l2):                \n                dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1], dp[i][j] + (text1[i]==text2[j]))\n        return dp[-1][-1]\n", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        dp = [[0 for i in range(len(text1)+1)] for j in range(len(text2)+1)]\n        for i in range(1, len(text2)+1):\n            for j in range(1, len(text1)+1):\n                if text2[i-1] == text1[j-1]:\n                    dp[i][j] = 1 + dp[i-1][j-1]\n                else:\n                    dp[i][j] = max(dp[i][j-1], dp[i-1][j])\n        print(dp)\n        return dp[-1][-1]\n", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        dp=[[-1 for i in range(len(text2)+1)]for j in range(len(text1)+1)]\n        for i in range(len(text1)+1):\n            for j in range(len(text2)+1):\n                if i==0 or j==0:\n                    dp[i][j]=0\n        for i in range(1,len(text1)+1):\n            for j in range(1,len(text2)+1):\n                if text1[i-1]==text2[j-1]:\n                    dp[i][j]=dp[i-1][j-1]+1\n                else:\n                    dp[i][j]=max(dp[i-1][j],dp[i][j-1])\n        return dp[len(text1)][len(text2)]", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        l1, l2 = len(text1), len(text2)\n        if l1 == 0 or l2 == 0:\n            return 0\n        dp = [0 for _ in range(l1+1)]\n        for i in range(l2):\n            temp = [n for n in dp]\n            curMax = 0\n            for j in range(1, l1+1):\n                if temp[j-1] > curMax:\n                    curMax = temp[j-1]\n                if text2[i] == text1[j-1]:\n                    dp[j] = curMax + 1\n            \n        return max(dp)\n        \n", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        L1 = len(text1)\n        L2 = len(text2)\n        dp = [[0 for _ in range(L2 + 1)] for _ in range(L1 + 1)]\n        \n        for i in range(1, L1 + 1):\n            for j in range(1, L2 + 1):\n                if text1[i - 1] == text2[j - 1]:\n                    dp[i][j] = dp[i - 1][j - 1] + 1\n                else:\n                    dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1])\n        \n        return dp[-1][-1]", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        \n        \n        dp = [[0 for j in range(len(text2))] for i in range(len(text1))]\n        \n        for i in range(len(text1)):\n            for j in range(len(text2)):\n                if text1[i] == text2[j]:\n                    if not i or not j:\n                        dp[i][j] = 1\n                    else:\n                        dp[i][j] = dp[i-1][j-1] + 1\n                else:\n                    if i:\n                        dp[i][j] = dp[i-1][j]\n                    if j:\n                        dp[i][j] = max(dp[i][j],dp[i][j-1])\n                        \n        return dp[-1][-1]", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        s1=text1\n        s2=text2\n        if len(s1)==0 or len(s2)==0:\n            return 0\n        rows=len(s1)+1\n        cols=len(s2)+1\n        arr=[[0 for i in range(cols)] for j in range(rows)]\n        for i in range(len(s1)):\n            for j in range(len(s2)):\n                if s1[i]==s2[j]:\n                    arr[i+1][j+1]=arr[i][j]+1\n                if s1[i]!=s2[j]:\n                    arr[i+1][j+1]=max(arr[i][j+1],arr[i+1][j])\n        return(arr[-1][-1])\n", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        n,m=len(text1),len(text2)\n        dp = [[0 for i in range(m+1)] for j in range(n+1)]\n        for i in range(1,n+1):\n            for j in range(1,m+1):\n                if text1[i-1]==text2[j-1]:\n                    dp[i][j]=dp[i-1][j-1]+1\n                else:\n                    dp[i][j]=max(dp[i-1][j],dp[i][j-1])\n        return dp[n][m]", "class Solution:\n    def longestCommonSubsequence(self, a: str, b: str) -> int:\n        m, n = len(a), len(b)\n        dp = [[0 for _ in range(n)] for _ in range(m)]\n        for i in range(m):\n            for j in range(n):\n                if a[i] == b[j]:\n                    dp[i][j] = 1 + (dp[i - 1][j - 1] if i - 1 >= 0 and j - 1 >= 0 else 0)\n                else:\n                    dp[i][j] = max(dp[i][j - 1] if j - 1 >= 0 else 0, dp[i - 1][j] if i - 1 >= 0 else 0)\n        print(dp)\n        return dp[-1][-1]", "class Solution:\n    \n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        ## recurrsion => lead to time exceeded\n        # if not text1 or not text2:\n        #     return 0            \n        # if text1[-1]==text2[-1]:\n        #     return 1+self.longestCommonSubsequence(text1[0:-1],text2[0:-1])\n        # elif text1[-1] != text2[-1]:\n        #     t1 = self.longestCommonSubsequence(text1,text2[0:-1])\n        #     t2 = self.longestCommonSubsequence(text1[0:-1],text2)\n        #     return max(t1,t2)\n        ## memorized method \n#         n = len(text1)\n#         m = len(text2)\n#         arr = [[0] * (m+1) for _ in range(n+1)]\n#         return self.LCS(text1,text2,n,m,arr)\n        \n#     def LCS(self,text1,text2,n,m,arr):\n#         if arr[n][m]:\n#             return arr[n][m]\n#         if n==0 or m==0:\n#             res = 0\n#         elif text1[n-1]==text2[m-1]:\n#             res = 1+self.LCS(text1,text2,n-1,m-1,arr)\n#         else:\n#             t1 = self.LCS(text1,text2,n,m-1,arr)\n#             t2 = self.LCS(text1,text2,n-1,m,arr)\n#             res = max(t1,t2)\n#         arr[n][m] = res\n#         return res\n        # bottom-up method\n        n,m = len(text1), len(text2)\n        arr = [[0]*(m+1) for _ in range(n+1)]\n        for i in range(n+1):\n            for j in range(m+1):\n                if i==0 or j==0:\n                    arr[i][j] = 0\n                elif text1[i-1]==text2[j-1]:\n                    arr[i][j] = 1 + arr[i-1][j-1]\n                else:\n                    arr[i][j] = max(arr[i-1][j],arr[i][j-1])\n        return arr[-1][-1] # arr[-1][-1]\n", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        \n        d = [[None] * (len(text2)+1) for _ in range(len(text1)+1)] \n        for j in range(len(text2)+1):\n            d[0][j] = 0\n        for i in range(len(text1)+1):\n            d[i][0] = 0\n        i = 1\n        while i < len(text1) + 1:\n            j = 1\n            while j < len(text2) + 1:\n                if text1[i-1] == text2[j-1]:\n                    d[i][j] = max(d[i-1][j-1] + 1, d[i][j-1], d[i-1][j])\n                else:\n                    d[i][j] = max(d[i][j-1], d[i-1][j])\n                j += 1\n            i += 1\n        return max([max(row) for row in d])\n            \n", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        \n        table={}\n        def helper(t1, t2, i,j, table):\n            if table.get((i,j)) != None:\n                return table[(i,j)]\n            \n            n = len(t1)\n            m = len(t2)\n            \n            if m <=j or n <= i:\n                return 0;     \n            \n            v = t1[i]\n            idx = t2.find(v, j)\n            if idx != -1:\n                r = max(helper(t1, t2, i+1, j, table), helper(t1, t2, i+1, idx+1, table)+1)\n                table[(i,j)] = r \n            else:\n                r = helper(t1, t2, i+1,j, table)\n                table[(i,j)] = r\n            return table[(i,j)]\n        \n        return helper(text1, text2, 0, 0, table)\n    \n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        n = len(text1)\n        m = len(text2)\n        \n        dp=[]\n        for v in range(n+1):\n            dp.append([-1]*(m+1))\n        \n        dp[0][0] = 0\n        for i in range(n+1):\n            dp[i][0] = 0\n        for j in range(m+1):\n            dp[0][j] = 0\n        for i in range(1,n+1):\n            for j in range(1, m+1):\n                v1=text1[i-1]\n                v2 = text2[j-1]\n                if v1 == v2:\n                    dp[i][j] = max(dp[i-1][j-1]+1, dp[i-1][j], dp[i][j-1])\n                else:\n                    dp[i][j] = max(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])\n        return dp[n][m]\n", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        \n        if not text1 or not text2:\n            return 0\n        \n        dp = [[0 for col in range(len(text2)+1)] for row in range(len(text1)+1)]\n        \n        for i in range(1,len(text1)+1):\n            for j in range(1,len(text2)+1):\n                options = [dp[i][j-1],dp[i-1][j]]\n                if text1[i-1] == text2[j-1]:\n                    options.append(dp[i-1][j-1]+1)\n                dp[i][j] = max(options)\n        return dp[-1][-1]", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        ################\n        dp = [0]*(len(text2)+1)\n        for i in range(1, len(text1)+1):\n            prev = dp[0]\n            for j in range(1, len(text2)+1):\n                last = dp[j]\n                if text1[i-1]==text2[j-1]:\n                    dp[j] = prev+1\n                if last>prev:\n                    prev = last\n        return max(dp)", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        m = len(text1)\n        n = len(text2)\n        memo = [[0 for _ in range(m)] for _ in range(n)]\n        res = 0\n        for row in range(n):\n            if row == 0 and text2[row] == text1[0]:\n                memo[row][0] = 1\n            else:\n                memo[row][0] = memo[row-1][0]\n            \n                if text2[row] == text1[0]:\n                    memo[row][0] = 1\n       \n        \n        for col in range(m):\n            if col == 0 and text1[col] == text2[0]:\n                memo[0][col] = 1\n            else:\n                memo[0][col] = memo[0][col-1]\n            \n                if text1[col] == text2[0]:\n                    memo[0][col] = 1\n        print(memo)\n        for row in range(1, n):\n            for col in range(1, m):\n                if text1[col] != text2[row]:\n                    memo[row][col] = max(memo[row-1][col],\n                                         memo[row][col-1],\n                                         memo[row-1][col-1])\n                else:\n                    memo[row][col] = 1 + min(memo[row-1][col],\n                                         memo[row][col-1],\n                                         memo[row-1][col-1])\n        \n        return memo[-1][-1]\n                \n        \n", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        width,depth = len(text1),len(text2)\n        dp = [[0 for _ in range(width)] for _ in range(depth)]\n        for i in range(depth):\n            for j in range(width):\n                if i == 0 and j == 0:\n                    dp[i][j] = 0\n                if i == 0:\n                    up = 0\n                else:\n                    up = dp[i-1][j]\n                if j == 0:\n                    left = 0\n                else:\n                    left = dp[i][j - 1]\n                if (text2[i] == text1[j]):\n                    if i == 0 or j == 0:\n                        dp[i][j] = 1\n                    else:\n                        dp[i][j] = dp[i-1][j-1] + 1\n                else:\n                    dp[i][j] = max(left,up)\n        for d in dp:print(d)\n        return dp[-1][-1]", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        # dp[i][j]\n        # represents what is the maximum up to that i and j included\n        dp = [[0] * (len(text2) + 1) for _ in range(len(text1) + 1)]\n        max_ = 0\n        for i in range(len(text1)-1, -1, -1):\n            for j in range(len(text2)-1, -1, -1):\n                dp[i][j] = max(dp[i+1][j], dp[i][j+1])\n                if text1[i] == text2[j]:\n                    dp[i][j] = max(dp[i+1][j+1] + 1, dp[i][j])\n                max_ = max(max_, dp[i][j])\n        return max_", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        dp= [[0]*(len(text2)+1) for _ in range((len(text1)+1))]\n        count=0\n        for r in range(1, len(dp)):\n            for c in range(1, len(dp[0])):\n                if text1[r-1]==text2[c-1]:\n                    dp[r][c]= dp[r-1][c-1]+1\n                else:\n                    dp[r][c]= max(dp[r-1][c], dp[r][c-1])\n                    \n                count= max(count,dp[r][c])\n                \n        return count\n", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        n = len(text1)\n        m = len(text2)\n        dp = [[0 for _ in range(m)] for _ in range(n)]\n        \n        #i -> text2\n        #j -> text1\n        for i in range(n):\n            for j in range(m):\n                # Need to do j-1, i-1, otherwise we would start from 1\n                # on both strings\n                if text1[i] == text2[j]:\n                    dp[i][j] = 1 + (0 if i-1 < 0 or j-1 < 0 else dp[i-1][j-1])\n                else:\n                    if i-1 > -1:\n                        dp[i][j] = dp[i-1][j]\n                    if j-1 > -1:\n                        dp[i][j] = max(dp[i][j], dp[i][j-1])\n\n        return dp[-1][-1]\n", "class Solution:\n    def longestCommonSubsequence(self, a: str, b: str) -> int:\n        m, n = len(a), len(b)\n        c = [[0 for _ in range(n + 1)] for _ in range(m + 1)]\n        for i in range(m + 1):\n            for j in range(n + 1):\n                if i == 0 or j == 0: c[i][j] = 0\n                else:\n                    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])\n                    else: c[i][j] = max([c[i - 1][j], c[i][j - 1]])\n        return c[m][n]\n", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        s1, s2 = len(text1), len(text2)\n        # init \n        res = 0\n        dp = [[0 for _ in range(s2+1)] for _ in range(s1+1)]\n        # dp[i][j] = dp[i-1][j-1] + 1 if text1[i]==text2[j] \n        #            dp[i-1][j-1]      else \n\n        for i in range(1, s1+1):\n            for j in range(1, s2+1):\n                if text1[i-1]==text2[j-1]:\n                    dp[i][j] = dp[i-1][j-1] + 1\n                else:\n                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])\n                res = max(dp[i][j], res)\n        return res\n        # boundary: 0 <= max_common <= min(len(tex1), len(text2))         \n", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        m = len(text1)\n        n = len(text2)\n        dp = [[0 for _ in range(n + 1)] for _ in range(m + 1)]\n        for i in range(1, m + 1):\n            for j in range(1, n + 1):\n                if text1[i - 1] == text2[j - 1]:\n                    dp[i][j] = dp[i - 1][j - 1] + 1\n                else:\n                    dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])\n        return dp[m][n]", "class Solution:\n    def longestCommonSubsequence(self, A: str, B: str) -> int:\n        if not A or not B:\n            return 0\n        \n        m, n = len(A), len(B)\n        f = [[None] * (n + 1) for _ in range(m + 1)]\n        \n        for i in range(m + 1):\n            for j in range(n + 1):\n                f[i][j] = 0\n                if i == 0 or j == 0:\n                    continue\n                \n                f[i][j] = max(f[i][j], f[i - 1][j], f[i][j - 1])\n                \n                if A[i - 1] == B[j - 1]:\n                    f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1)\n        \n        return f[m][n]\n", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        \n        lengthone= len(text1)\n        lengthtwo= len(text2)\n        \n        n = 1000\n        ans = [[0]*n for _ in range(n)]\n        \n        for i in range(lengthone):\n            for j in range(lengthtwo):\n                if text1[i]==text2[j]:\n                    ans[i][j]=ans[i-1][j-1]+1\n                else:\n                    ans[i][j]=max(ans[i-1][j],ans[i][j-1])\n        \n        return ans[lengthone-1][lengthtwo-1]\n\n#         if ans[len(text1)][len(text2)] != 0:\n#             return ans[len(text1)][len(text2)]\n\n#         elif len(text1) == 0 or len(text2) == 0:\n#             return 0\n\n#         elif text1[-1] == text2[-1]:\n#             ans[len(text1)][len(text2)] = LCS(text1[:-1], text2[:-1]) + 1\n#             return ans[len(text1)][len(text2)]\n\n#         else:\n#             ans[len(text1)][len(text2)] = max(\n#                 LCS(text1[:-1], text2), LCS(text1, text2[:-1]))\n#             return ans[len(text1)][len(text2)]\n\n\n#         text1 = \\\"This code is a sample text for longest common subsequence\\\"\n#         text2 = \\\"abcde\\\"\n\n#         LCS(text1, text2)\n\n#         print(\\\"LCS of {} and {} = {}\\\".format(text1, text2, LCS(text1, text2)))\n\n", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        if not text1: return 0\n        \n        l = len(text1)\n        n = next((i for i, c in enumerate(text1) if c == text2[0]), l)\n        commonSubstrings = [0] * n + [1] * (l - n)\n\n        for c2 in text2[1:]:\n            tmp = [0] * l\n            tmp[0] = int(c2 == text1[0] or commonSubstrings[0])\n            for i, c1 in enumerate(text1[1:], 1):\n                if c1 == c2:\n                    tmp[i] = commonSubstrings[i - 1] + 1\n                else:\n                    tmp[i] = max(tmp[i - 1], commonSubstrings[i])\n            commonSubstrings = tmp\n\n        return commonSubstrings[-1]\n", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        #Top Down recursion - only works with LRU Cache\n        @lru_cache(None)\n        def helper(idx1, idx2):\n            if len(text1) <= idx1 or len(text2) <= idx2:\n                return 0\n            if text1[idx1] == text2[idx2]:\n                return 1 + helper(idx1+1, idx2+1)\n            if text1[idx1] not in text2[idx2:]:\n                return helper(idx1+1, idx2)\n            else:\n                newidx2 = idx2 + text2[idx2:].index(text1[idx1])\n                return max(helper(idx1+1,newidx2+1) + 1, helper(idx1+1, idx2))\n        return helper(0,0)\n        \n        \n", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        dp = [ [0 for _ in range(len(text1) + 1)] for _ in range(len(text2) + 1) ];\n        to_return = 0;\n        for i in range(len(text2)):\n            for j in range(len(text1)):\n                r, c = i + 1, j + 1\n                if(text1[j] == text2[i]):\n                    dp[r][c] = 1 + dp[r-1][c-1]\n                else:\n                    dp[r][c] = max(dp[r-1][c], dp[r][c-1])\n         \n                to_return = max(to_return, dp[r][c]);\n        return to_return;\n        \n", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n#            '' a. c. e \n#         ''  0 0. 0. 0.\n#         a   0 1  0. 0\n#         b   0 1  \n#         c   0 1  \n#         d   0\n#         e   0\n        \n        if len(text1) == 0 or len(text2) == 0: return ''\n        DP = [[0]*(len(text1)+1) for _ in range(len(text2)+1)]\n        \n        longest = 0\n        for i in range(1,len(text2)+1):\n            for j in range(1,len(text1)+1):\n                if text2[i-1] == text1[j-1]:\n                    DP[i][j] = max(max(DP[i-1][j-1]+1, DP[i-1][j]),DP[i][j-1])\n                else:\n                    DP[i][j] = max(DP[i-1][j],DP[i][j-1])\n                longest = max(longest, DP[i][j])\n                \n        # print(DP)\n        return longest", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        @lru_cache(None)\n        def helper(idx1, idx2):\n            if len(text1) <= idx1 or len(text2) <= idx2:\n                return 0\n            if text1[idx1] == text2[idx2]:\n                return 1 + helper(idx1+1, idx2+1)\n            if text1[idx1] not in text2[idx2:]:\n                return helper(idx1+1, idx2)\n            else:\n                newidx2 = idx2 + text2[idx2:].index(text1[idx1])\n                return max(helper(idx1+1,newidx2+1) + 1, helper(idx1+1, idx2))\n        return helper(0,0)\n        \n        \n", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        D = []\n        for i in range(len(text1) + 1):\n            D.append([0] * (len(text2) + 1))\n        \n        for i in range(1, len(text1) + 1):\n            for j in range(1, len(text2) + 1):\n                delta = 1 if text1[i-1] == text2[j-1] else 0\n                D[i][j] = max(D[i-1][j], D[i][j-1], D[i-1][j-1] + delta)\n        \n        return D[len(text1)][len(text2)]\n", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        if len(text2) > len(text1):\n            text1,text2=text2,text1\n        pre = [0] * (len(text1)+1)\n        cur = [0] * (len(text2)+1)\n        \n        for col in reversed(list(range(len(text1)))):\n            for row in reversed(list(range(len(text2)))):\n                if (text1[col] == text2[row]):\n                    cur[row] = 1 + pre[row+1]\n                else:\n                    cur[row] = max(pre[row],cur[row + 1])\n            pre, cur = cur, pre\n        return pre[0]\n                    \n            \n            \n        \n", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        if len(text2) > len(text1):\n            text1, text2 = text2, text1\n        dp = [[0] * (len(text1)+1) for _ in range(len(text2)+1)]\n        for i in range(1, len(text2)+1):\n            for j in range(1, len(text1)+1):\n                max_sides = max(dp[i-1][j], dp[i][j-1])\n                if text1[j-1] == text2[i-1]:\n                    dp[i][j] = max(dp[i-1][j-1] + 1, max_sides)\n                else:\n                    dp[i][j] = max(dp[i-1][j-1], max_sides)\n        return dp[-1][-1]", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        text1 = list(text1)\n        text2 = list(text2)\n        n = len(text1)\n        m = len(text2)\n        dp = [[0 for i in range(m+1)] for i in range(n+1)]\n        for i in range(1,n+1):\n            for j in range(1,m+1):\n                if text1[i-1] == text2[j-1]:\n                    dp[i][j] = 1+dp[i-1][j-1]\n                else:\n                    dp[i][j] = max(dp[i-1][j],dp[i][j-1])\n        return dp[n][m]\n        \n    \n        \n", "class Solution:\n    def longestCommonSubsequence(self, s1: str, s2: str) -> int:\n        if s1 == '' or s2 == '':\n            return 0\n        dp = [[0 for y in s2] for x in s1]\n        for i in range(0, len(s1)):\n            for j in range(0, len(s2)):\n                if i == 0 and j == 0:\n                    dp[i][j] = 1 if s1[i] == s2[j] else 0\n                elif i == 0:\n                    dp[i][j] = 1 if s1[i] == s2[j] else dp[i][j - 1]\n                elif j == 0:\n                    dp[i][j] = 1 if s1[i] == s2[j] else dp[i - 1][j]\n                else:\n                    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]])\n        \n        return dp[-1][-1]\n        \n        \n        \n        \n        \n", "import numpy as np\nclass Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) :\n        dp = np.full((len(text1)+1,len(text2)+1),0)\n        print((dp.shape))\n        for i in range(dp.shape[0]-2,-1,-1) :\n            for j in range(dp.shape[1]-2,-1,-1) :\n                if(text1[i]==text2[j]) :\n                    dp[i,j] = 1 + dp[i+1][j+1]\n                    \n                else :\n                    dp[i,j] = max(dp[i+1,j],dp[i,j+1])\n                    \n        return dp[0,0]\n            \n        \n", "class Solution:\n    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n        len_1, len_2 = len(text1), len(text2)\n        # Append an additional 0 to stand for the case of \\\"\\\" for both strings\n        dp = [[0] * (len_2 + 1) for _ in range(len_1 + 1)]\n        max_len_subseq = 0\n        \n        for j in range(1, len_2 + 1):\n            for i in range(1, len_1 + 1):\n                if text1[i-1] == text2[j-1]:\n                    dp[i][j] = dp[i-1][j-1] + 1\n                else:\n                    dp[i][j] = max(dp[i][j-1], dp[i-1][j])  \n                max_len_subseq = max(max_len_subseq, dp[i][j])\n        return max_len_subseq"]