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.

Source: leetcode | Difficulty: MEDIUM
Tags: String algorithms

Dynamic programming

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

Solutions:
class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

	def recursiveLCS(self, t1, t2):
		if not t1 or not t2:
			return 0
		elif t1[0] == t2[0]:
			return 1 + self.recursiveLCS(t1[1:], t2[1:])
		else:
			left = self.recursiveLCS(t1[1:], t2)
			right = self.recursiveLCS(t1, t2[1:])
			return max(left, right)

	def recursiveLongestCommonSubsequence(self, text1: str, text2: str) -> int:
		return self.recursiveLCS(text1, text2)

	def longestCommonSubsequence(self, text1: str, text2: str) -> int:
		DP = [[0] * (len(text2) + 1) for i in range(len(text1) + 1)]
		for i in range(1, len(text1) + 1):
			for j in range(1, len(text2) + 1):
				if text1[i - 1] == text2[j - 1]:
					DP[i][j] = 1 + DP[i - 1][j - 1]
				else:
					left = DP[i - 1][j]
					right = DP[i][j - 1]
					DP[i][j] = max(left, right)
		for row in DP:
			print(row)
		return DP[len(text1)][len(text2)]


from collections import defaultdict

class Solution:

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


class Solution:

	def longestCommonSubsequence(self, text1: str, text2: str) -> int:
		(str1, str2) = (text1, text2)
		num_rows = len(str1) + 1
		num_cols = len(str2) + 1
		lengths = [[0 for _ in range(num_cols)] for _ in range(num_rows)]
		for row in range(1, num_rows):
			for col in range(1, num_cols):
				if str1[row - 1] == str2[col - 1]:
					lengths[row][col] = lengths[row - 1][col - 1] + 1
				else:
					lengths[row][col] = max(lengths[row - 1][col], lengths[row][col - 1])
		return lengths[-1][-1]


import numpy as np

class Solution:

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


class Solution:

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


class Solution:

	def longestCommonSubsequence(self, s1: str, s2: str) -> int:

		def print_grid(grid):
			for row in grid:
				print(row)
		dp_row = [0] * (len(s2) + 1)
		dp_row_pre = [0] * (len(s2) + 1)
		(N, M) = (len(s1), len(s2))
		for i in range(N - 1, -1, -1):
			for j in range(M - 1, -1, -1):
				if s1[i] == s2[j]:
					dp_row[j] = dp_row_pre[j + 1] + 1
				else:
					dp_row[j] = max(dp_row_pre[j], dp_row[j + 1])
			(dp_row_pre, dp_row) = (dp_row, dp_row_pre)
		return dp_row_pre[0]


from functools import lru_cache

class Solution:

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


class Solution:

	def longestCommonSubsequence(self, s1, s2):

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


class Solution:

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


class Solution:

	def longestCommonSubsequence(self, text1: str, text2: str) -> int:
		n = len(text1)
		m = len(text2)
		dp = []
		for i in range(n):
			dp.append([-1] * m)

		def lcs(i, j):
			if i >= n or j >= m:
				return 0
			if dp[i][j] != -1:
				return dp[i][j]
			if text1[i] == text2[j]:
				ans = 1 + lcs(i + 1, j + 1)
			else:
				ans = max(lcs(i + 1, j), lcs(i, j + 1))
			dp[i][j] = ans
			return ans
		return lcs(0, 0)


class Solution:

	def longestCommonSubsequence(self, text1, text2):

		def compute(x, y):
			if x == len(text1):
				return 0
			if y == len(text2):
				return 0
			if text1[x] == text2[y]:
				return 1 + compute(x + 1, y + 1)
			return max([compute(x + 1, y), compute(x, y + 1)])
		cache = {}
		for x in range(-1, len(text1) + 1):
			cache[x, -1] = 0
		for y in range(-1, len(text2) + 1):
			cache[-1, y] = 0
		for x in range(len(text1)):
			for y in range(len(text2)):
				if text1[x] == text2[y]:
					cache[x, y] = 1 + cache[x - 1, y - 1]
				else:
					cache[x, y] = max([cache[x, y - 1], cache[x - 1, y]])
		return cache[len(text1) - 1, len(text2) - 1]


class Solution:

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


class Solution:

	def longestCommonSubsequence(self, text1: str, text2: str) -> int:
		memo = [[-1] * (len(text2) + 1) for _ in range(len(text1) + 1)]
		return self.helper(text1, text2, 0, 0, memo)

	def helper(self, s1, s2, i, j, memo):
		if memo[i][j] != -1:
			return memo[i][j]
		if i == len(s1) or j == len(s2):
			return 0
		ans = 0
		if s1[i] == s2[j]:
			ans = 1 + self.helper(s1, s2, i + 1, j + 1, memo)
		else:
			ans = max(self.helper(s1, s2, i + 1, j, memo), self.helper(s1, s2, i, j + 1, memo))
		memo[i][j] = ans
		return ans


from functools import lru_cache

class Solution:

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

		@lru_cache(None)
		def lcs(idxA, idxB):
			if idxA < 0 or idxB < 0:
				return 0
			if text1[idxA] == text2[idxB]:
				return 1 + lcs(idxA - 1, idxB - 1)
			return max(lcs(idxA - 1, idxB), lcs(idxA, idxB - 1))
		return lcs(len(text1) - 1, len(text2) - 1)


class Solution:

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


class Solution:

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


class Solution:

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

		def helper(i, j):
			if memo[i][j] == None:
				if i == n1 or j == n2:
					memo[i][j] = 0
				elif a[i] == b[j]:
					return 1 + helper(i + 1, j + 1)
				else:
					memo[i][j] = max(helper(i, j + 1), helper(i + 1, j))
			return memo[i][j]
		return helper(0, 0)


from collections import defaultdict

class Solution:

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

		@lru_cache(maxsize=None)
		def helper(n, m):
			if m < 0 or n < 0:
				return 0
			if text1[n] == text2[m]:
				length = 1 + helper(n - 1, m - 1)
			else:
				length = max(helper(n - 1, m), helper(n, m - 1))
			return length
		return helper(len(text1) - 1, len(text2) - 1)


class Solution:

	def longestCommonSubsequence(self, text1: str, text2: str) -> int:
		import functools

		@functools.lru_cache(None)
		def helper(i, j):
			if i < 0 or j < 0:
				return 0
			if text1[i] == text2[j]:
				return helper(i - 1, j - 1) + 1
			return max(helper(i - 1, j), helper(i, j - 1))
		return helper(len(text1) - 1, len(text2) - 1)


class Solution:

	def longestCommonSubsequence(self, text1: str, text2: str) -> int:
		(m, n) = (len(text1), len(text2))

		@lru_cache(None)
		def find(i, j):
			if i >= m or j >= n:
				return 0
			if text1[i] == text2[j]:
				return 1 + find(i + 1, j + 1)
			else:
				return max(find(i + 1, j), find(i, j + 1))
		return find(0, 0)


from functools import lru_cache

class Solution:

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

		@lru_cache(maxsize=None)
		def memo(l1, l2):
			if l1 == len(text1) or l2 == len(text2):
				return 0
			if text1[l1] == text2[l2]:
				return 1 + memo(l1 + 1, l2 + 1)
			else:
				return max(memo(l1 + 1, l2), memo(l1, l2 + 1))
		return memo(0, 0)


class Solution:

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

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


from functools import lru_cache as memoize

class Solution:

	def longestCommonSubsequence(self, s1, s2):

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


class Solution:

	def longestCommonSubsequence(self, text1: str, text2: str) -> int:
		from functools import lru_cache

		@lru_cache(maxsize=None)
		def memo_solve(p1, p2):
			if p1 == len(text1) or p2 == len(text2):
				return 0
			if text1[p1] == text2[p2]:
				return 1 + memo_solve(p1 + 1, p2 + 1)
			else:
				return max(memo_solve(p1, p2 + 1), memo_solve(p1 + 1, p2))
		return memo_solve(0, 0)


class Solution:

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

		@lru_cache(maxsize=None)
		def memo_solve(index1, index2):
			if index1 == len(text1) or index2 == len(text2):
				return 0
			if text1[index1] == text2[index2]:
				return 1 + memo_solve(index1 + 1, index2 + 1)
			else:
				return max(memo_solve(index1, index2 + 1), memo_solve(index1 + 1, index2))
		return memo_solve(0, 0)


class Solution:

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

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


class Solution:

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


class Solution:

	def longestCommonSubsequence(self, text1: str, text2: str) -> int:
		from functools import lru_cache

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


class Solution:

	def longestCommonSubsequence(self, s1: str, s2: str) -> int:

		@lru_cache(None)
		def helper(i, j):
			if i == len(s1) or j == len(s2):
				return 0
			if s1[i] == s2[j]:
				return 1 + helper(i + 1, j + 1)
			else:
				return max(helper(i + 1, j), helper(i, j + 1))
		return helper(0, 0)


class Solution:

	def longestCommonSubsequence(self, text1: str, text2: str) -> int:
		n = len(text1)
		m = len(text2)
		self.store = [[-1 for i in range(m)] for j in range(n)]
		self.Rec(text1, text2, n - 1, m - 1)
		return self.store[-1][-1]

	def Rec(self, text1, text2, n, m):
		if n < 0 or m < 0:
			return 0
		if self.store[n][m] != -1:
			return self.store[n][m]
		if text1[n] == text2[m]:
			x = 1 + self.Rec(text1, text2, n - 1, m - 1)
			self.store[n][m] = x
		else:
			x = max(self.Rec(text1, text2, n - 1, m), self.Rec(text1, text2, n, m - 1))
			self.store[n][m] = x
		return x


class Solution:

	def longestCommonSubsequence(self, text1: str, text2: str) -> int:
		memorize = [[-1] * (len(text2) + 1) for _ in range(len(text1) + 1)]

		def LCS(i1, i2):
			if i1 >= len(text1) or i2 >= len(text2):
				return 0
			if memorize[i1][i2] != -1:
				return memorize[i1][i2]
			if text1[i1] == text2[i2]:
				memorize[i1][i2] = 1 + LCS(i1 + 1, i2 + 1)
			else:
				memorize[i1][i2] = max(LCS(i1, i2 + 1), LCS(i1 + 1, i2))
			return memorize[i1][i2]
		ans = LCS(0, 0)
		return ans


from typing import List

class Solution:

	def longestCommonSubsequence(self, text1: str, text2: str) -> int:
		dp: List[List[int]] = []
		for i in range(len(text1)):
			dp.append(len(text2) * [-1])

		def cal_with_cache(i: int, j: int):
			if i < 0 or j < 0:
				return 0
			if dp[i][j] == -1:
				dp[i][j] = cal(i, j)
			return dp[i][j]

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


class Solution:

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


from functools import lru_cache

class Solution:

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

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


class Solution:

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

	def lcs(self, t1, i, t2, j, memo):
		if i >= len(t1) or j >= len(t2):
			return 0
		elif memo[i][j] != -1:
			return memo[i][j]
		else:
			result = -1
			if t1[i] == t2[j]:
				result = 1 + self.lcs(t1, i + 1, t2, j + 1, memo)
			else:
				result = max(self.lcs(t1, i + 1, t2, j, memo), self.lcs(t1, i, t2, j + 1, memo))
			memo[i][j] = result
			return result


from functools import lru_cache

class Solution:

	def longestCommonSubsequence(self, text1: str, text2: str) -> int:
		if len(text1) == 0 or len(text2) == 0:
			return 0
		t1_idx = len(text1) - 1
		t2_idx = len(text2) - 1

		@lru_cache(maxsize=2147483647)
		def lcs(t1_idx, t2_idx):
			if t1_idx == -1 or t2_idx == -1:
				return 0
			if text1[t1_idx] == text2[t2_idx]:
				return 1 + lcs(t1_idx - 1, t2_idx - 1)
			else:
				return max(lcs(t1_idx, t2_idx - 1), lcs(t1_idx - 1, t2_idx))
		return lcs(t1_idx, t2_idx)


class Solution:

	def longestCommonSubsequence(self, s1, s2):

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


class Solution:

	def longestCommonSubsequence(self, text1: str, text2: str) -> int:
		memo = [[-1 for i in range(len(text2))] for i in range(len(text1))]

		def memoSolve(i, j):
			if i == len(text1) or j == len(text2):
				return 0
			if memo[i][j] >= 0:
				return memo[i][j]
			answer = 0
			if text1[i] == text2[j]:
				answer = 1 + memoSolve(i + 1, j + 1)
			else:
				answer = max(memoSolve(i + 1, j), memoSolve(i, j + 1))
			memo[i][j] = answer
			return memo[i][j]
		return memoSolve(0, 0)


class Solution:

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


class Solution:

	def __init__(self):
		self.dp = None

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

	def lcs_rec(self, x, y, n, m):
		if n == 0 or m == 0:
			return 0
		if self.dp[n][m] != -1:
			return self.dp[n][m]
		if x[n - 1] == y[m - 1]:
			self.dp[n][m] = 1 + self.lcs_rec(x, y, n - 1, m - 1)
		else:
			self.dp[n][m] = max(self.lcs_rec(x, y, n - 1, m), self.lcs_rec(x, y, n, m - 1))
		return self.dp[n][m]


class Solution:

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

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


class Solution:

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

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


class Solution:

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


class Solution:

	def longestCommonSubsequence(self, text1: str, text2: str) -> int:
		if not text1 or not text2:
			return 0
		cacheRow = [None] * len(text2)
		cache = [cacheRow[:] for i in range(len(text1))]
		return self.dp(text1, text2, 0, 0, cache)

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


class Solution:

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


class Solution:

	def longestCommonSubsequence(self, text1: str, text2: str) -> int:
		dp = [[-1] * len(text2) for _ in range(len(text1))]

		def lcsForCell(i, j):
			if i < 0 or j < 0:
				return 0
			if dp[i][j] != -1:
				return dp[i][j]
			if text1[i] == text2[j]:
				dp[i][j] = lcsForCell(i - 1, j - 1) + 1
			else:
				dp[i][j] = max(lcsForCell(i - 1, j), lcsForCell(i, j - 1))
			return dp[i][j]
		return lcsForCell(len(text1) - 1, len(text2) - 1)


class Solution:

	def longestCommonSubsequence(self, text1: str, text2: str) -> int:
		n1 = len(text1)
		n2 = len(text2)
		memo = {}

		def lcs(pointer1, pointer2):
			if (pointer1, pointer2) in memo:
				return memo[pointer1, pointer2]
			if pointer1 >= n1 or pointer2 >= n2:
				return 0
			if text1[pointer1] == text2[pointer2]:
				x = 1 + lcs(pointer1 + 1, pointer2 + 1)
			else:
				x = max(lcs(pointer1 + 1, pointer2), lcs(pointer1, pointer2 + 1))
			memo[pointer1, pointer2] = x
			return x
		return lcs(0, 0)


class Solution:

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


class Solution:

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

		def solve(i, j):
			if i == n or j == m:
				return 0
			if memo[i][j] != -1:
				return memo[i][j]
			if text1[i] == text2[j]:
				memo[i][j] = 1 + solve(i + 1, j + 1)
			else:
				memo[i][j] = max(solve(i, j + 1), solve(i + 1, j))
			return memo[i][j]
		(n, m) = (len(text1), len(text2))
		memo = [[-1 for _ in range(m)] for _ in range(n)]
		return solve(0, 0)


class Solution:

	def longestCommonSubsequence(self, text1: str, text2: str) -> int:
		memo = [[-1] * (len(text2) + 1) for _ in range(len(text1) + 1)]

		def dfs(t1, t2):
			(n1, n2) = (len(t1), len(t2))
			if memo[n1][n2] != -1:
				return memo[n1][n2]
			if n1 == 0 or n2 == 0:
				return 0
			if t1[-1] == t2[-1]:
				res = dfs(t1[:-1], t2[:-1]) + 1
			else:
				res = max(dfs(t1[:-1], t2), dfs(t1, t2[:-1]))
			memo[n1][n2] = res
			return res
		dfs(text1, text2)
		return memo[-1][-1]


class Solution:

	def longestCommonSubsequence(self, text1: str, text2: str) -> int:
		self.n = len(text1)
		self.m = len(text2)
		self.text1 = text1
		self.text2 = text2
		self.table = []
		for i in range(self.n):
			self.table.append([-1] * self.m)
		return self.longest(0, 0)

	def longest(self, i, j):
		if i == self.n or j == self.m:
			return 0
		if self.table[i][j] != -1:
			return self.table[i][j]
		else:
			if self.text1[i] == self.text2[j]:
				self.table[i][j] = 1 + self.longest(i + 1, j + 1)
			else:
				self.table[i][j] = max(self.longest(i + 1, j), self.longest(i, j + 1))
			return self.table[i][j]


from functools import lru_cache

class Solution:

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


class Solution:

	def longestCommonSubsequence(self, s1: str, s2: str) -> int:
		dp = [[0] * (len(s2) + 1) for _ in range(len(s1) + 1)]
		for s1_index in range(len(s1)):
			for s2_index in range(len(s2)):
				if s1[s1_index] != s2[s2_index]:
					dp[s1_index + 1][s2_index + 1] = max(dp[s1_index][s2_index + 1], dp[s1_index + 1][s2_index], dp[s1_index][s2_index])
				else:
					dp[s1_index + 1][s2_index + 1] = max(dp[s1_index][s2_index + 1], dp[s1_index + 1][s2_index], dp[s1_index][s2_index] + 1)
		return dp[-1][-1]


class Solution:

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

		@lru_cache(maxsize=None)
		def memo_solve(p1, p2):
			if p1 == len(text1) or p2 == len(text2):
				return 0
			option_1 = memo_solve(p1 + 1, p2)
			first_occurence = text2.find(text1[p1], p2)
			option_2 = 0
			if first_occurence != -1:
				option_2 = 1 + memo_solve(p1 + 1, first_occurence + 1)
			return max(option_1, option_2)
		return memo_solve(0, 0)


class Solution:

	def lcs(self, text1, text2, i1, i2, memo):
		if len(text1) == i1 or len(text2) == i2:
			return 0
		if memo[i1][i2] != -1:
			return memo[i1][i2]
		if text1[i1] == text2[i2]:
			memo[i1][i2] = 1 + self.lcs(text1, text2, i1 + 1, i2 + 1, memo)
			return memo[i1][i2]
		maxLen = 0
		maxLen = max(maxLen, self.lcs(text1, text2, i1 + 1, i2, memo))
		maxLen = max(maxLen, self.lcs(text1, text2, i1, i2 + 1, memo))
		memo[i1][i2] = maxLen
		return maxLen

	def longestCommonSubsequence(self, text1: str, text2: str) -> int:
		memo = [[-1 for _ in range(len(text2))] for _ in range(len(text1))]
		maxLen = self.lcs(text1, text2, 0, 0, memo)
		return maxLen


class Solution:

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

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


class Solution:

	def longestCommonSubsequence(self, text1: str, text2: str) -> int:
		mem = {}

		def dfs(l, r):
			if (l, r) in mem:
				return mem[l, r]
			if l == len(text1) or r == len(text2):
				return 0
			ans = 0
			if text1[l] == text2[r]:
				ans = 1 + dfs(l + 1, r + 1)
			else:
				ans = max(dfs(l + 1, r), dfs(l, r + 1))
			mem[l, r] = ans
			return ans
		return dfs(0, 0)


class Solution:

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


class Solution:

	def longestCommonSubsequence(self, text1: str, text2: str) -> int:
		dp = {}

		def lcs(left, right):
			nonlocal text1
			nonlocal text2
			if (left, right) in dp:
				return dp[left, right]
			if left >= len(text1) or right >= len(text2):
				return 0
			if text1[left] == text2[right]:
				count = 1 + lcs(left + 1, right + 1)
				dp[left, right] = count
				return count
			else:
				count = max(lcs(left + 1, right), lcs(left, right + 1))
				dp[left, right] = count
				return count
		return lcs(0, 0)


class Solution:

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

		def dpRecurse(i: int, j: int):
			result = 0
			if (i, j) in memo:
				return memo[i, j]
			if i >= len(text1) or j >= len(text2):
				return 0
			elif text1[i] == text2[j]:
				result = 1 + dpRecurse(i + 1, j + 1)
			else:
				result = max(dpRecurse(i + 1, j), dpRecurse(i, j + 1))
			memo[i, j] = result
			return result
		return dpRecurse(0, 0)


from functools import lru_cache

class Solution:

	def longestCommonSubsequence(self, txt1: str, txt2: str) -> int:

		@lru_cache(maxsize=None)
		def rec(i, j):
			if i == -1 or j == -1:
				return 0
			if txt1[i] == txt2[j]:
				return rec(i - 1, j - 1) + 1
			if txt1[i] != txt2[j]:
				return max(rec(i - 1, j), rec(i, j - 1))
		return rec(len(txt1) - 1, len(txt2) - 1)


class Solution:

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

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


class Solution:

	def longestCommonSubsequence(self, text1: str, text2: str) -> int:
		return self.find({}, 0, 0, text1, text2)

	def find(self, memo, i, j, text1, text2):
		if (i, j) in memo:
			return memo[i, j]
		if i == len(text1):
			return 0
		if j == len(text2):
			return 0
		if text1[i] == text2[j]:
			memo[i, j] = self.find(memo, i + 1, j + 1, text1, text2) + 1
		else:
			memo[i, j] = max(self.find(memo, i, j + 1, text1, text2), self.find(memo, i + 1, j, text1, text2))
		return memo[i, j]


from functools import lru_cache

class Solution:

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

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


import math

class Solution:

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


class Solution:

	def longestCommonSubsequence(self, text1: str, text2: str) -> int:
		memo = {}
		return self.helper(0, 0, text1, text2, memo)

	def helper(self, index_1, index_2, text1, text2, memo):
		if index_1 == len(text1) or index_2 == len(text2):
			return 0
		elif (index_1, index_2) in memo:
			return memo[index_1, index_2]
		else:
			if text1[index_1] == text2[index_2]:
				ans = 1 + self.helper(index_1 + 1, index_2 + 1, text1, text2, memo)
			else:
				ans = max(self.helper(index_1 + 1, index_2, text1, text2, memo), self.helper(index_1, index_2 + 1, text1, text2, memo))
			memo[index_1, index_2] = ans
			return ans


class Solution:

	def longestCommonSubsequence(self, text1: str, text2: str) -> int:
		hist = {}

		def helper(str1, str2, m, n):
			if (m, n) in hist:
				return hist[m, n]
			if m == 0 or n == 0:
				return 0
			elif str1[m - 1] == str2[n - 1]:
				hist[m, n] = 1 + helper(str1, str2, m - 1, n - 1)
				return hist[m, n]
			hist[m, n] = max(helper(str1, str2, m - 1, n), helper(str1, str2, m, n - 1))
			return hist[m, n]
		return helper(text1, text2, len(text1), len(text2))


class Solution:

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

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


import numpy as np

class Solution:

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


class Solution:

	def longestCommonSubsequence(self, text1: str, text2: str) -> int:
		memo = [[-1 for i in range(len(text2))] for i in range(len(text1))]

		def memoSolve(i, j):
			if i == len(text1) or j == len(text2):
				return 0
			if memo[i][j] >= 0:
				return memo[i][j]
			include = 0
			j2 = text2.find(text1[i], j)
			if j2 != -1:
				include = 1 + memoSolve(i + 1, j2 + 1)
			noTake = memoSolve(i + 1, j)
			memo[i][j] = max(include, noTake)
			return memo[i][j]
		return memoSolve(0, 0)


from functools import wraps

class Solution:

	def longestCommonSubsequence(self, text1, text2):

		def cache_decorator(f):
			_cache = {}

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

		@cache_decorator
		def compute(x, y):
			if x == len(text1):
				return 0
			if y == len(text2):
				return 0
			if text1[x] == text2[y]:
				return 1 + compute(x + 1, y + 1)
			return max([compute(x + 1, y), compute(x, y + 1)])
		return compute(0, 0)


class Solution:

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

		def lcs_helper(index1, index2, memo={}):
			if index1 == len(text1) or index2 == len(text2):
				return 0
			key = (index1, index2)
			if key not in memo:
				if text1[index1] == text2[index2]:
					memo[key] = 1 + lcs_helper(index1 + 1, index2 + 1, memo)
				else:
					memo[key] = max(lcs_helper(index1, index2 + 1, memo), lcs_helper(index1 + 1, index2, memo))
			return memo[key]
		return lcs_helper(0, 0)


class Solution:

	def longestCommonSubsequence(self, text1: str, text2: str) -> int:
		cache = {}

		def dfs(i, j, count):
			if i == len(text1) or j == len(text2):
				return 0
			if (i, j) in cache:
				return cache[i, j]
			if text1[i] == text2[j]:
				return 1 + dfs(i + 1, j + 1, count)
			a = dfs(i + 1, j, count)
			b = dfs(i, j + 1, count)
			c = max(a, b)
			cache[i, j] = c
			return c
		return dfs(0, 0, 0)


class Solution:

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

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


class Solution:

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

		def recurse(i1, i2):
			if i1 >= len(text1) or i2 >= len(text2):
				return 0
			if (i1, i2) in memo:
				return memo[i1, i2]
			if text1[i1] == text2[i2]:
				memo[i1, i2] = 1 + recurse(i1 + 1, i2 + 1)
			else:
				memo[i1, i2] = max(recurse(i1 + 1, i2), recurse(i1, i2 + 1))
			return memo[i1, i2]
		return recurse(0, 0)


class Solution:

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


class Solution:

	def longestCommonSubsequence(self, text1: str, text2: str) -> int:
		memo = dict()

		def solve(i, j):
			if i == len(text1) or j == len(text2):
				return 0
			if (i, j) in memo:
				return memo[i, j]
			if text1[i] == text2[j]:
				ans = 1 + solve(i + 1, j + 1)
			else:
				ans = max(solve(i + 1, j), solve(i, j + 1))
			memo[i, j] = ans
			return ans
		return solve(0, 0)


class Solution:

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


class Solution:

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

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


class Solution:

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

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


class Solution:

	def longestCommonSubsequence(self, text1: str, text2: str) -> int:
		self.memo = {}
		self.t1 = text1
		self.t2 = text2
		tup = (len(text1), len(text2))
		return self.helper(tup)

	def helper(self, tup):
		if tup in self.memo:
			return self.memo[tup]
		elif tup[0] == 0 or tup[1] == 0:
			return 0
		elif self.t1[tup[0] - 1] == self.t2[tup[1] - 1]:
			x = (tup[0] - 1, tup[1] - 1)
			self.memo[tup] = 1 + self.helper(x)
		else:
			a = (tup[0] - 1, tup[1])
			b = (tup[0], tup[1] - 1)
			self.memo[tup] = max(self.helper(a), self.helper(b))
		return self.memo[tup]


class Solution:

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

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


class Solution:

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

	def helper(self, s1, s2, i, j, memo):
		if memo[i][j] < 0:
			if i == len(s1) or j == len(s2):
				memo[i][j] = 0
			elif s1[i] == s2[j]:
				memo[i][j] = 1 + self.helper(s1, s2, i + 1, j + 1, memo)
			else:
				memo[i][j] = max(self.helper(s1, s2, i + 1, j, memo), self.helper(s1, s2, i, j + 1, memo))
		return memo[i][j]

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

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


class Solution:

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

		@lru_cache(maxsize=None)
		def helper(i1, i2):
			if i1 == len(text1) or i2 == len(text2):
				return 0
			else:
				if text1[i1] == text2[i2]:
					return helper(i1 + 1, i2 + 1) + 1
				return max(helper(i1 + 1, i2), helper(i1, i2 + 1))
		return helper(0, 0)


from collections import defaultdict

class Solution:

	def longestCommonSubsequence(self, text1: str, text2: str) -> int:
		dp = defaultdict(lambda : -1)

		def helper(n, m):
			if m < 0 or n < 0:
				return 0
			if dp[m, n] == -1:
				if text1[n] == text2[m]:
					length = 1 + helper(n - 1, m - 1)
				else:
					length = max(helper(n - 1, m), helper(n, m - 1))
				dp[m, n] = length
			return dp[m, n]
		return helper(len(text1) - 1, len(text2) - 1)


class Solution:

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

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


class Solution:
	import functools

	def longestCommonSubsequence(self, text1: str, text2: str) -> int:
		longest = 0
		memo = {}

		def calc_lcs(i, j):
			if i < 0 or j < 0:
				return 0
			if (i, j) in memo:
				return memo[i, j]
			if text1[i] == text2[j]:
				return 1 + calc_lcs(i - 1, j - 1)
			memo[i, j] = max(calc_lcs(i, j - 1), calc_lcs(i - 1, j))
			return memo[i, j]
		return calc_lcs(len(text1) - 1, len(text2) - 1)


from functools import lru_cache

class Solution:

	def longestCommonSubsequence(self, text1: str, text2: str) -> int:
		if not text1 or not text2:
			return 0
		(n, m) = (len(text1), len(text2))

		@lru_cache(maxsize=10000)
		def lcs(i, j):
			if i > n - 1 or j > m - 1:
				return 0
			if text1[i] == text2[j]:
				return lcs(i + 1, j + 1) + 1
			return max(lcs(i + 1, j), lcs(i, j + 1))
		return lcs(0, 0)


class Solution:

	def longestCommonSubsequence(self, text1: str, text2: str) -> int:
		if not text1 or not text2:
			return 0
		(n, m) = (len(text1), len(text2))
		M = {}
		ret = 0

		def dp(i, j):
			if i >= n or j >= m:
				return 0
			if (i, j) in M:
				return M[i, j]
			M[i, j] = 0
			if text1[i] == text2[j]:
				M[i, j] = 1 + dp(i + 1, j + 1)
			else:
				M[i, j] = max(dp(i + 1, j), dp(i, j + 1))
			return M[i, j]
		return dp(0, 0)


class Solution:

	def longestCommonSubsequence(self, text1: str, text2: str) -> int:
		dp = dict()
		return self.top_down(dp, text1, text2, 0, 0)

	def recursive(self, text1, text2, i, j):
		if i >= len(text1) or j >= len(text2):
			return 0
		if text1[i] == text2[j]:
			return 1 + self.recursive(text1, text2, i + 1, j + 1)
		a = self.recursive(text1, text2, i + 1, j)
		b = self.recursive(text1, text2, i, j + 1)
		return max(a, b)

	def top_down(self, dp, text1, text2, i, j):
		if i >= len(text1) or j >= len(text2):
			return 0
		if text1[i] == text2[j]:
			return 1 + self.top_down(dp, text1, text2, i + 1, j + 1)
		if (i, j) in dp:
			return dp[i, j]
		a = self.top_down(dp, text1, text2, i + 1, j)
		b = self.top_down(dp, text1, text2, i, j + 1)
		dp[i, j] = max(a, b)
		return dp[i, j]

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


class Solution:

	def longestCommonSubsequence(self, text1: str, text2: str) -> int:
		mp = {}

		def lcs(i, j):
			if i >= len(text1) or j >= len(text2):
				return 0
			elif (i, j) in mp:
				return mp[i, j]
			else:
				if text1[i] == text2[j]:
					mp[i, j] = 1 + lcs(i + 1, j + 1)
				else:
					mp[i, j] = max(lcs(i + 1, j), lcs(i, j + 1))
				return mp[i, j]
		lcs(0, 0)
		return max(mp.values())


class Solution:

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

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


class Solution:

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


class Solution:

	def longestCommonSubsequence(self, text1: str, text2: str) -> int:
		if len(text1) == 0 or len(text2) == 0:
			return 0
		mem = [[-1 for _ in range(len(text2) + 1)] for _ in range(len(text1) + 1)]
		return self.compute(mem, 0, 0, text1, text2)

	def compute(self, mem, ptr1, ptr2, text1, text2):
		if ptr1 == len(text1) or ptr2 == len(text2):
			return 0
		if mem[ptr1][ptr2] != -1:
			return mem[ptr1][ptr2]
		if text1[ptr1] == text2[ptr2]:
			ans = 1 + self.compute(mem, ptr1 + 1, ptr2 + 1, text1, text2)
			mem[ptr1][ptr2] = ans
			return ans
		else:
			ans = max(self.compute(mem, ptr1 + 1, ptr2, text1, text2), self.compute(mem, ptr1, ptr2 + 1, text1, text2))
			mem[ptr1][ptr2] = ans
			return ans


class Solution:

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

		def helper(s1, s2, i1, i2):
			if not s1 or not s2:
				return 0
			if (i1, i2) in memo:
				return memo[i1, i2]
			if s1[0] == s2[0]:
				memo[i1, i2] = 1 + helper(s1[1:], s2[1:], i1 + 1, i2 + 1)
			else:
				memo[i1, i2] = max(helper(s1[1:], s2, i1 + 1, i2), helper(s1, s2[1:], i1, i2 + 1))
			return memo[i1, i2]
		return helper(text1, text2, 0, 0)


class Solution:

	def longestCommonSubsequence(self, text1: str, text2: str) -> int:
		cache = [[-1 for _ in range(len(text2))] for _ in range(len(text1))]

		def lcs(text1, text2, i, j, cache):
			if i >= len(text1) or j >= len(text2):
				return 0
			if cache[i][j] != -1:
				return cache[i][j]
			elif text1[i] == text2[j]:
				return 1 + lcs(text1, text2, i + 1, j + 1, cache)
			else:
				cache[i][j] = max(lcs(text1, text2, i, j + 1, cache), lcs(text1, text2, i + 1, j, cache))
				return cache[i][j]
		a = lcs(text1, text2, 0, 0, cache)
		return a


class Solution:

	def longestCommonSubsequence(self, text1: str, text2: str) -> int:
		cache = {}

		def solve(t1, t2):
			if t1 == len(text1) or t2 == len(text2):
				return 0
			if (t1, t2) in cache:
				return cache[t1, t2]
			if text1[t1] == text2[t2]:
				opt1 = solve(t1 + 1, t2 + 1)
				cache[t1 + 1, t2 + 1] = opt1
				return 1 + opt1
			else:
				opt1 = solve(t1, t2 + 1)
				opt2 = solve(t1 + 1, t2)
				cache[t1, t2 + 1] = opt1
				cache[t1 + 1, t2] = opt2
				return max(opt1, opt2)
		return solve(0, 0)


from functools import lru_cache

class Solution:

	def longestCommonSubsequence(self, text1: str, text2: str) -> int:
		(t1, t2) = (text1, text2)

		@lru_cache(None)
		def lcsh(m, n):
			nonlocal t1, t2
			if m == 0 or n == 0:
				return 0
			if t1[m - 1] == t2[n - 1]:
				return 1 + lcsh(m - 1, n - 1)
			else:
				return max(lcsh(m - 1, n), lcsh(m, n - 1))
		return lcsh(len(text1), len(text2))


class Solution:

	def lcs(self, i, j):
		if (i, j) not in self.memo:
			if i == len(self.s) or j == len(self.p):
				ans = 0
			elif self.s[i] == self.p[j]:
				ans = self.lcs(i + 1, j + 1) + 1
			else:
				ans = max(self.lcs(i + 1, j), self.lcs(i, j + 1))
			self.memo[i, j] = ans
		return self.memo[i, j]

	def longestCommonSubsequence(self, text1: str, text2: str) -> int:
		(self.s, self.p) = (text1, text2)
		self.memo = {}
		return self.lcs(0, 0)


class Solution:

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


class Solution:

	def longestCommonSubsequence(self, text1: str, text2: str) -> int:
		dp = [-1] * len(text1)
		for i in range(len(dp)):
			dp[i] = [-1] * len(text2)
		self.dp = dp
		self.t1 = text1
		self.t2 = text2
		return self.LCSHelper(len(text1) - 1, len(text2) - 1)

	def LCSHelper(self, i, j):
		if i < 0 or i >= len(self.t1) or j < 0 or (j >= len(self.t2)):
			return 0
		if self.dp[i][j] != -1:
			return self.dp[i][j]
		if self.t1[i:i + 1] == self.t2[j:j + 1]:
			self.dp[i][j] = 1 + self.LCSHelper(i - 1, j - 1)
		else:
			self.dp[i][j] = max(self.LCSHelper(i, j - 1), self.LCSHelper(i - 1, j))
		return self.dp[i][j]


class Solution:

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

		def lcs(i, j):
			if (i, j) in memo:
				return memo[i, j]
			if i == len(text1) or j == len(text2):
				return 0
			move_both = None
			if text1[i] == text2[j]:
				move_both = 1 + lcs(i + 1, j + 1)
			move_i = lcs(i + 1, j)
			move_j = lcs(i, j + 1)
			memo[i, j] = max(move_i, move_j) if move_both is None else max([move_i, move_j, move_both])
			return memo[i, j]
		return lcs(0, 0)


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

class Solution:

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


class Solution:

	def longestCommonSubsequence(self, s1: str, s2: str) -> int:

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


class Solution:

	def longestCommonSubsequence(self, text1: str, text2: str) -> int:
		t = [[-1 for j in range(len(text2) + 1)] for i in range(len(text1) + 1)]
		for i in range(len(text1) + 1):
			for j in range(len(text2) + 1):
				t[0][j] = 0
				t[i][0] = 0
		res = self.LCS(text1, text2, len(text1), len(text2), t)
		return res

	def LCS(self, s1, s2, n, m, t):
		if t[n][m] != -1:
			return t[n][m]
		elif s1[n - 1] == s2[m - 1]:
			t[n][m] = self.LCS(s1, s2, n - 1, m - 1, t) + 1
			return t[n][m]
		elif s1[n - 1] != s2[m - 1]:
			t[n][m] = max(self.LCS(s1, s2, n - 1, m, t), self.LCS(s1, s2, n, m - 1, t))
			return t[n][m]


class Solution:

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


class Solution:

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


class Solution:

	def __init__(self):
		self.d = {}

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

		def lcs(p1, p2):
			if p1 == len(text1) or p2 == len(text2):
				return 0
			if (p1, p2) not in self.d:
				if text1[p1] == text2[p2]:
					res = 1 + lcs(p1 + 1, p2 + 1)
				else:
					res = max(lcs(p1 + 1, p2), lcs(p1, p2 + 1))
				self.d[p1, p2] = res
			return self.d[p1, p2]
		return lcs(0, 0)


class Solution:

	def longestCommonSubsequence(self, text1: str, text2: str) -> int:
		cache = [[None for j in range(len(text2))] for i in range(len(text1))]
		self.memo(text1, text2, 0, 0, cache)
		return cache[0][0]

	def memo(self, word1, word2, i, j, cache):
		if i >= len(word1) or j >= len(word2):
			return 0
		if word1[i] == word2[j]:
			if cache[i][j] is None:
				cache[i][j] = 1 + self.memo(word1, word2, i + 1, j + 1, cache)
			return cache[i][j]
		else:
			if cache[i][j] is None:
				cache[i][j] = max(self.memo(word1, word2, i + 1, j, cache), self.memo(word1, word2, i, j + 1, cache))
			return cache[i][j]


class Solution:

	def longestCommonSubsequence(self, text1: str, text2: str) -> int:
		dp = {}

		def inner(i, j):
			if i >= len(text1) or j >= len(text2):
				return 0
			if dp.get((i, j)) == None:
				if text1[i] == text2[j]:
					dp[i, j] = inner(i + 1, j + 1) + 1
				else:
					dp[i, j] = max(inner(i + 1, j), inner(i, j + 1))
			return dp[i, j]
		return inner(0, 0)


class Solution:

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


from functools import lru_cache

class Solution:

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

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


class Solution:

	def longestCommonSubsequence(self, text1: str, text2: str) -> int:
		dp = dict()
		return self.top_down(dp, text1, text2, 0, 0)

	def recursive(self, text1, text2, i, j):
		if i >= len(text1) or j >= len(text2):
			return 0
		if text1[i] == text2[j]:
			return 1 + self.recursive(text1, text2, i + 1, j + 1)
		a = self.recursive(text1, text2, i + 1, j)
		b = self.recursive(text1, text2, i, j + 1)
		return max(a, b)

	def top_down(self, dp, text1, text2, i, j):
		if i >= len(text1) or j >= len(text2):
			return 0
		if text1[i] == text2[j]:
			return 1 + self.top_down(dp, text1, text2, i + 1, j + 1)
		if (i, j) in dp:
			return dp[i, j]
		a = self.top_down(dp, text1, text2, i + 1, j)
		b = self.top_down(dp, text1, text2, i, j + 1)
		dp[i, j] = max(a, b)
		return max(a, b)


class Solution:

	def longestCommonSubsequence(self, text1: str, text2: str) -> int:
		table = {}

		def helper(t1, t2, i, j, table):
			if table.get((i, j)) != None:
				return table[i, j]
			n = len(t1)
			m = len(t2)
			if m <= j or n <= i:
				return 0
			v = t1[i]
			idx = t2.find(v, j)
			if idx != -1:
				r = max(helper(t1, t2, i + 1, j, table), helper(t1, t2, i + 1, idx + 1, table) + 1)
				table[i, j] = r
			else:
				r = helper(t1, t2, i + 1, j, table)
				table[i, j] = r
			return table[i, j]
		return helper(text1, text2, 0, 0, table)


class Solution:

	def longestCommonSubsequence(self, text1: str, text2: str) -> int:
		map = {}

		def memo(p1, p2, map):
			if (p1, p2) in map:
				return map[p1, p2]
			else:
				if p1 == len(text1) or p2 == len(text2):
					return 0
				if text1[p1] == text2[p2]:
					map[p1, p2] = 1 + memo(p1 + 1, p2 + 1, map)
				else:
					map[p1, p2] = max(memo(p1, p2 + 1, map), memo(p1 + 1, p2, map))
				return map[p1, p2]
		return memo(0, 0, map)


class Solution:

	def longestCommonSubsequence(self, text1: str, text2: str) -> int:
		lookup = [[None for x in range(len(text2))] for y in range(len(text1))]

		def helper(s1, s2, pos1, pos2):
			nonlocal lookup
			if pos1 >= len(s1):
				return 0
			elif pos2 >= len(s2):
				return 0
			elif lookup[pos1][pos2] is not None:
				return lookup[pos1][pos2]
			elif s1[pos1] == s2[pos2]:
				lookup[pos1][pos2] = max(1 + helper(s1, s2, pos1 + 1, pos2 + 1), helper(s1, s2, pos1 + 1, pos2 + 1), helper(s1, s2, pos1, pos2 + 1), helper(s1, s2, pos1 + 1, pos2))
				return lookup[pos1][pos2]
			else:
				lookup[pos1][pos2] = max(helper(s1, s2, pos1 + 1, pos2 + 1), helper(s1, s2, pos1, pos2 + 1), helper(s1, s2, pos1 + 1, pos2))
				return lookup[pos1][pos2]
		return helper(text1, text2, 0, 0)


class Solution:

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

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


class Solution:

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


class Solution:

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


class Solution:

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

		def memo(f):
			dic = {}

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

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


import numpy as np

class Solution:

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


from functools import lru_cache

class Solution:

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

		@lru_cache(None)
		def helper(t1, t2):
			if not t1 or not t2:
				return 0
			if t1[-1] == t2[-1]:
				return helper(t1[:-1], t2[:-1]) + 1
			else:
				return max(helper(t1[:-1], t2), helper(t1, t2[:-1]))
		return helper(text1, text2)


class Solution:

	def longestCommonSubsequence(self, text1: str, text2: str) -> int:
		self.dp = {}
		return self.recursiveLCS(text1, text2, len(text1) - 1, len(text2) - 1)

	def recursiveLCS(self, text1, text2, p1, p2):
		if p1 < 0 or p2 < 0:
			return 0
		if (p1, p2) in self.dp:
			self.dp[p1, p2] = self.dp[p1, p2]
			return self.dp[p1, p2]
		if text1[p1] == text2[p2]:
			self.dp[p1, p2] = 1 + self.recursiveLCS(text1, text2, p1 - 1, p2 - 1)
		else:
			self.dp[p1, p2] = max(self.recursiveLCS(text1, text2, p1 - 1, p2), self.recursiveLCS(text1, text2, p1, p2 - 1))
		return self.dp[p1, p2]


from typing import *

class Solution:

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

def longestCommonSubsequence_DP(text1: str, text2: str, first_start_idx: int, second_start_idx: int, memo: Dict):
	if (first_start_idx, second_start_idx) in memo:
		return memo[first_start_idx, second_start_idx]
	if first_start_idx == len(text1) or second_start_idx == len(text2):
		return 0
	first_cur_char = text1[first_start_idx]
	second_cur_char = text2[second_start_idx]
	ans_if_cur_same = -1
	if first_cur_char == second_cur_char:
		ans_if_cur_same = 1 + longestCommonSubsequence_DP(text1, text2, first_start_idx + 1, second_start_idx + 1, memo)
	ans1_if_cur_diff = longestCommonSubsequence_DP(text1, text2, first_start_idx, second_start_idx + 1, memo)
	ans2_if_cur_diff = longestCommonSubsequence_DP(text1, text2, first_start_idx + 1, second_start_idx, memo)
	memo[first_start_idx, second_start_idx] = max(ans_if_cur_same if ans_if_cur_same != -1 else -math.inf, ans1_if_cur_diff, ans2_if_cur_diff)
	return memo[first_start_idx, second_start_idx]


class Solution:

	def longestCommonSubsequence(self, text1: str, text2: str) -> int:
		self.cache = [[-1] * len(text2) for _ in range(len(text1))]

		def findSubsequence(idx1, idx2):
			if idx1 == len(text1) or idx2 == len(text2):
				return 0
			if self.cache[idx1][idx2] != -1:
				return self.cache[idx1][idx2]
			res = 0
			if text1[idx1] == text2[idx2]:
				res = 1 + findSubsequence(idx1 + 1, idx2 + 1)
			else:
				res = max(findSubsequence(idx1 + 1, idx2), findSubsequence(idx1, idx2 + 1))
			self.cache[idx1][idx2] = res
			return res
		return findSubsequence(0, 0)


from functools import lru_cache

class Solution:

	def longestCommonSubsequence(self, text1: str, text2: str) -> int:
		(self.text1, self.text2) = (text1, text2)
		return self.lcs(0, 0)

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


from functools import lru_cache

class Solution:

	def longestCommonSubsequence(self, text1: str, text2: str) -> int:
		self.text1 = text1
		self.text2 = text2
		return self.solve(len(text1), len(text2))

	@lru_cache(None)
	def solve(self, m, n):
		if not m or not n:
			return 0
		if self.text1[m - 1] == self.text2[n - 1]:
			return 1 + self.solve(m - 1, n - 1)
		else:
			return max(self.solve(m - 1, n), self.solve(m, n - 1))


class Solution:

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

		@lru_cache(maxsize=None)
		def LCS(t1, t2):
			if len(t1) == 0 or len(t2) == 0:
				return 0
			elif t1[-1] == t2[-1]:
				return LCS(t1[0:-1], t2[0:-1]) + 1
			else:
				return max(LCS(t1[0:-1], t2), LCS(t1, t2[0:-1]))
		return LCS(text1, text2)


class Solution:

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


class Solution:

	def longestCommonSubsequence(self, text1: str, text2: str) -> int:
		record = [[0 for _ in range(len(text2))] for _ in range(len(text1))]

		def f(s1, s2, i, j):
			if i >= len(s1) or j >= len(s2):
				return 0
			if record[i][j] > 0:
				return record[i][j]
			if s1[i] == s2[j]:
				temp = 1 + f(s1, s2, i + 1, j + 1)
			else:
				temp = max(f(s1, s2, i, j + 1), f(s1, s2, i + 1, j))
			record[i][j] = temp
			return record[i][j]
		f(text1, text2, 0, 0)
		return record[0][0]


class Solution:

	def longestCommonSubsequence(self, text1: str, text2: str) -> int:
		dp = [[-1] * (len(text2) + 1) for i in range(len(text1) + 1)]

		def LCS(s1, s2, n, m, dp):
			if n == 0 or m == 0:
				return 0
			if dp[n - 1][m - 1] != -1:
				return dp[n - 1][m - 1]
			if s1[n - 1] == s2[m - 1]:
				dp[n - 1][m - 1] = 1 + LCS(s1, s2, n - 1, m - 1, dp)
				return dp[n - 1][m - 1]
			else:
				dp[n - 1][m - 1] = max(LCS(s1, s2, n - 1, m, dp), LCS(s1, s2, n, m - 1, dp))
				return dp[n - 1][m - 1]
		return LCS(text1, text2, len(text1), len(text2), dp)


from functools import lru_cache

class Solution:

	def longestCommonSubsequence(self, text1: str, text2: str) -> int:
		n1 = len(text1)
		n2 = len(text2)

		@lru_cache(None)
		def dp(s1, s2):
			if len(s1) == 0 or len(s2) == 0:
				return 0
			elif s1[0] == s2[0]:
				return 1 + dp(s1[1:], s2[1:])
			return max(dp(s1[1:], s2), dp(s1, s2[1:]))
		return dp(text1, text2)


import numpy as np
from functools import lru_cache

class Solution:

	def longestCommonSubsequence(self, text1: str, text2: str) -> int:
		if len(text1) == 0 or len(text2) == 0:
			return 0
		m = len(text1)
		n = len(text2)
		return self.dp(text1, text2, m - 1, n - 1)

	@lru_cache(maxsize=None)
	def dp(self, text1, text2, i, j):
		if i < 0 or j < 0:
			return 0
		if text1[i] == text2[j]:
			return self.dp(text1, text2, i - 1, j - 1) + 1
		else:
			return max(self.dp(text1, text2, i - 1, j), self.dp(text1, text2, i, j - 1))


class Solution:

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

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


class Solution:

	def longestCommonSubsequence(self, text1: str, text2: str) -> int:
		memo = [[0] * (len(text2) + 1) for i in range(len(text1) + 1)]
		s1 = text1
		s2 = text2

		def helper(i1, i2):
			if memo[i1][i2]:
				return memo[i1][i2]
			if i1 == len(s1) or i2 == len(s2):
				return 0
			if s1[i1] == s2[i2]:
				memo[i1][i2] = 1 + helper(i1 + 1, i2 + 1)
			else:
				memo[i1][i2] = max(helper(i1 + 1, i2), helper(i1, i2 + 1))
			return memo[i1][i2]
		return helper(0, 0)


from functools import lru_cache

class Solution:

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

		@lru_cache(None)
		def lcs_of_sub(s1, s2):
			if not s1 or not s2:
				return 0
			(c1, c2) = (s1[-1], s2[-1])
			(sub1, sub2) = (s1[:-1], s2[:-1])
			if c1 == c2:
				return lcs_of_sub(sub1, sub2) + 1
			return max(lcs_of_sub(sub1, sub2), lcs_of_sub(sub1, s2), lcs_of_sub(s1, sub2))
		return lcs_of_sub(text1, text2)


class Solution:

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

		def LCS(s1, s2, i1, i2):
			if i1 > len(s1) - 1 or i2 > len(s2) - 1:
				return 0
			if (i1, i2) in memo:
				return memo[i1, i2]
			if s1[i1] == s2[i2]:
				memo[i1, i2] = 1 + LCS(s1, s2, i1 + 1, i2 + 1)
				return memo[i1, i2]
			s1_next = LCS(s1, s2, i1 + 1, i2)
			s2_next = LCS(s1, s2, i1, i2 + 1)
			memo[i1, i2] = max(s1_next, s2_next)
			return memo[i1, i2]
		return LCS(text1, text2, 0, 0)


class Solution:

	def longestCommonSubsequence(self, text1: str, text2: str) -> int:
		memo = [[None for i in range(len(text2) + 1)] for _ in range(len(text1) + 1)]

		def rec(i, j):
			if i == len(text1) or j == len(text2):
				return 0
			if text1[i] == text2[j]:
				if not memo[i + 1][j + 1]:
					memo[i + 1][j + 1] = rec(i + 1, j + 1)
				return 1 + memo[i + 1][j + 1]
			else:
				if not memo[i][j + 1]:
					memo[i][j + 1] = rec(i, j + 1)
				if not memo[i + 1][j]:
					memo[i + 1][j] = rec(i + 1, j)
				return max(memo[i][j + 1], memo[i + 1][j])
		return rec(0, 0)


class Solution:

	def __init__(self):
		self.cached = {}

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


class Solution:

	@lru_cache(maxsize=None)
	def longest(self, p1, p2):
		if p1 == len(self.t1) or p2 == len(self.t2):
			return 0
		if self.t1[p1] == self.t2[p2]:
			return 1 + self.longest(p1 + 1, p2 + 1)
		return max(self.longest(p1 + 1, p2), self.longest(p1, p2 + 1))

	def longestCommonSubsequence(self, text1: str, text2: str) -> int:
		self.t1 = text1
		self.t2 = text2
		return self.longest(0, 0)


class Solution:

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

		def checkPosition(i1, i2):
			if i1 == len(str1) or i2 == len(str2):
				return 0
			if cache[i1][i2] != -1:
				return cache[i1][i2]
			if str1[i1] == str2[i2]:
				keep = 1 + checkPosition(i1 + 1, i2 + 1)
			else:
				keep = -1
			skip1 = checkPosition(i1 + 1, i2)
			skip2 = checkPosition(i1, i2 + 1)
			best = max([keep, skip1, skip2])
			cache[i1][i2] = best
			return best
		return checkPosition(0, 0)


class Solution:

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

	def longestCommonSubsequence(self, s1: str, s2: str) -> int:
		return self._longest_common_subsequence(s1, s2, {})


class Solution:

	def longestCommonSubsequence(self, s1: str, s2: str) -> int:

		def rec(s1, s2, i, j, lcs):
			if i == len(s1) or j == len(s2):
				return 0
			if (i, j) in lcs:
				return lcs[i, j]
			else:
				if s1[i] == s2[j]:
					lcs[i, j] = 1 + rec(s1, s2, i + 1, j + 1, lcs)
				else:
					l = rec(s1, s2, i + 1, j, lcs)
					r = rec(s1, s2, i, j + 1, lcs)
					lcs[i, j] = max(l, r)
				return lcs[i, j]
		return rec(s1, s2, 0, 0, {})


class Solution:

	def longestCommonSubsequence(self, text1: str, text2: str) -> int:
		memo = [[-1 for i in range(len(text2))] for i in range(len(text1))]

		def memoSolve(i, j):
			if i == len(text1) or j == len(text2):
				return 0
			if memo[i][j] >= 0:
				return memo[i][j]
			includeHere = 0
			if text1[i] == text2[j]:
				includeHere = 1 + memoSolve(i + 1, j + 1)
			includeLater = memoSolve(i, j + 1)
			included = max(includeHere, includeLater)
			noTake = max(memoSolve(i + 1, j), memoSolve(i + 1, j + 1))
			memo[i][j] = max(included, noTake)
			return memo[i][j]
		return memoSolve(0, 0)


class Solution:

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

	def longestCommonSubsequence1(self, text1: str, text2: str) -> int:

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


class Solution:

	def helper(self, text1, text2, index1, index2, match):
		if index1 == len(text1) or index2 == len(text2):
			return match
		s1 = 0
		s2 = 0
		s3 = 0
		if text1[index1] == text2[index2]:
			s1 = self.helper(text1, text2, index1 + 1, index2 + 1, match + 1)
		else:
			s2 = self.helper(text1, text2, index1, index2 + 1, match)
			s3 = self.helper(text1, text2, index1 + 1, index2, match)
		return max(s1, s2, s3)

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


class Solution:

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


class Solution:

	def longestCommonSubsequence(self, text1: str, text2: str) -> int:
		L1 = len(text1)
		L2 = len(text2)
		A = [[0] * (L2 + 1) for i in range(L1 + 1)]
		Max = 0
		for i in range(L1, -1, -1):
			for j in range(L2, -1, -1):
				if i < L1 and j < L2:
					if text1[i] == text2[j]:
						A[i][j] = A[i + 1][j + 1] + 1
					else:
						A[i][j] = max(A[i][j + 1], A[i + 1][j])
				if Max < A[i][j]:
					Max = A[i][j]
		return A[i][j]


class Solution:

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


class Solution:

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


class Solution:

	def longestCommonSubsequence(self, s1: str, s2: str) -> int:
		dp_grid = [[0] * (len(s1) + 1) for _ in range(len(s2) + 1)]
		for r in range(len(s2) + 1):
			for c in range(len(s1) + 1):
				if r == 0 or c == 0:
					dp_grid[r][c] = 0
				elif s2[r - 1] == s1[c - 1]:
					dp_grid[r][c] = dp_grid[r - 1][c - 1] + 1
				else:
					dp_grid[r][c] = max(dp_grid[r - 1][c], dp_grid[r][c - 1])
		return dp_grid[-1][-1]


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

	def longestCommonSubsequence(self, text1: str, text2: str) -> int:
		table = {}

		def helper(t1, t2, i, j, table):
			if table.get((i, j)) != None:
				return table[i, j]
			n = len(t1)
			m = len(t2)
			if m <= j or n <= i:
				return 0
			v = t1[i]
			idx = t2.find(v, j)
			if idx != -1:
				r = max(helper(t1, t2, i + 1, j, table), helper(t1, t2, i + 1, idx + 1, table) + 1)
				table[i, j] = r
			else:
				r = helper(t1, t2, i + 1, j, table)
				table[i, j] = r
			return table[i, j]
		return helper(text1, text2, 0, 0, table)

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


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

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

		@lru_cache(None)
		def helper(idx1, idx2):
			if len(text1) <= idx1 or len(text2) <= idx2:
				return 0
			if text1[idx1] == text2[idx2]:
				return 1 + helper(idx1 + 1, idx2 + 1)
			if text1[idx1] not in text2[idx2:]:
				return helper(idx1 + 1, idx2)
			else:
				newidx2 = idx2 + text2[idx2:].index(text1[idx1])
				return max(helper(idx1 + 1, newidx2 + 1) + 1, helper(idx1 + 1, idx2))
		return helper(0, 0)


class Solution:

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


class Solution:

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


import numpy as np

class Solution:

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


class Solution:

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