Given two sequences, find the length of longest subsequence present in both of them. Both the strings are of uppercase.
Example 1:
Input:
A = 6, B = 6
str1 = ABCDGH
str2 = AEDFHR
Output: 3
Explanation: LCS for input Sequences
“ABCDGH” and “AEDFHR” is “ADH” of
length 3.
Example 2:
Input:
A = 3, B = 2
str1 = ABC
str2 = AC
Output: 2
Explanation: LCS of "ABC" and "AC" is
"AC" of length 2.
Your Task:
Complete the function lcs() which takes the length of two strings respectively and two strings as input parameters and returns the length of the longest subsequence present in both of them. 
Expected Time Complexity : O(|str1|*|str2|)
Expected Auxiliary Space: O(|str1|*|str2|)
Constraints:
1<=size(str1),size(str2)<=10^{3}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Dynamic programming

Starter code: #User function Template for python3



class Solution:

    

    #Function to find the length of longest common subsequence in two strings.

    def lcs(self,x,y,s1,s2):

        

        # code here

Solutions:
class Solution:

	def fun(self, s1, s2, x, y):
		maxi = 0
		l = [[0 for p in range(y + 1)] for o in range(x + 1)]
		for i in range(1, x + 1):
			for j in range(1, y + 1):
				if s1[i - 1] == s2[j - 1]:
					l[i][j] = l[i - 1][j - 1] + 1
				else:
					l[i][j] = max(l[i - 1][j], l[i][j - 1])
				if maxi < l[i][j]:
					maxi = l[i][j]
		return maxi

	def lcs(self, x, y, s1, s2):
		p = self.fun(s1, s2, x, y)
		return p


class Solution:

	def lcs(self, N, M, s1, s2):
		dp = [[0] * (M + 1) for _ in range(N + 1)]
		for i in range(N):
			for j in range(M):
				if s1[i] == s2[j]:
					dp[i + 1][j + 1] = 1 + dp[i][j]
				else:
					dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j])
		return dp[N][M]


class Solution:

	def lcs(self, x, y, s1, s2):
		dp = [[0] * (y + 1) for _ in range(x + 1)]
		for i in range(1, x + 1):
			for j in range(1, y + 1):
				if s1[i - 1] == s2[j - 1]:
					dp[i][j] = 1 + dp[i - 1][j - 1]
				else:
					dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
		return dp[x][y]


class Solution:

	def lcs(self, x, y, s1, s2):
		dp = {}

		def recursion(x, y):
			if x == 0 and y == 0:
				return 1 if s1[x] == s2[y] else 0
			if x < 0 or y < 0:
				return 0
			if (x, y) in dp:
				return dp[x, y]
			if s1[x] == s2[y]:
				dp[x, y] = 1 + recursion(x - 1, y - 1)
				return dp[x, y]
			dp[x, y] = max(recursion(x - 1, y), recursion(x, y - 1))
			return dp[x, y]
		return recursion(x - 1, y - 1)


class Solution:

	def lcs(self, m, n, seq1, seq2):
		dp = [[0] * (n + 1) for _ in range(m + 1)]
		for i in range(m):
			for j in range(n):
				if seq1[i] == seq2[j]:
					dp[i + 1][j + 1] = dp[i][j] + 1
				else:
					dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1])
		return dp[m][n]


class Solution:

	def lcs(self, x, y, s1, s2):
		dp = [[None] * (y + 1) for i in range(x + 1)]
		for i in range(x + 1):
			for j in range(y + 1):
				if i == 0 or j == 0:
					dp[i][j] = 0
				elif s1[i - 1] == s2[j - 1]:
					dp[i][j] = dp[i - 1][j - 1] + 1
				else:
					dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
		return dp[x][y]


class Solution:

	def lcs(self, x, y, text1, text2):
		dp = [[0 for i in range(len(text2) + 1)] for j in range(len(text1) + 1)]
		for i in range(len(text1) - 1, -1, -1):
			for j in range(len(text2) - 1, -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 lcs(self, x, y, s1, s2):
		import sys
		sys.setrecursionlimit(10 ** 9 + 7)
		n = len(s1)
		m = len(s2)
		dp = [[0 for j in range(m + 1)] for i in range(n + 1)]
		for i in range(1, n + 1):
			for j in range(1, m + 1):
				if s1[i - 1] == s2[j - 1]:
					dp[i][j] = 1 + dp[i - 1][j - 1]
				else:
					dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
		return dp[n][m]

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


class Solution:

	def lcs(self, x, y, s1, s2):
		arr = [[float('inf')] * (x + 1) for i in range(y + 1)]
		for i in range(x + 1):
			arr[0][i] = 0
		for j in range(y + 1):
			arr[j][0] = 0
		for i in range(1, y + 1):
			for j in range(1, x + 1):
				if s2[i - 1] == s1[j - 1]:
					arr[i][j] = arr[i - 1][j - 1] + 1
				else:
					arr[i][j] = max(arr[i - 1][j], arr[i][j - 1])
		return arr[y][x]


class Solution:

	def lcs(self, x, y, s1, s2):
		dp = [[-1] * (y + 1) for _ in range(x + 1)]
		return bottoms_up(x, y, s1, s2)
		return lcs_(x, y, s1, s2, dp)

def lcs_(x, y, s1, s2, dp) -> int:
	if x == 0 or y == 0:
		return 0
	if dp[x][y] != -1:
		return dp[x][y]
	if s1[x - 1] == s2[y - 1]:
		dp[x][y] = 1 + lcs_(x - 1, y - 1, s1, s2, dp)
	else:
		dp[x][y] = max(lcs_(x - 1, y, s1, s2, dp), lcs_(x, y - 1, s1, s2, dp))
	return dp[x][y]

def bottoms_up(x, y, s1, s2):
	dp = [[0] * (y + 1) for i in range(x + 1)]
	for i in range(1, x + 1):
		for j in range(1, y + 1):
			if s1[i - 1] == s2[j - 1]:
				dp[i][j] = 1 + dp[i - 1][j - 1]
			else:
				dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
	return dp[x][y]


class Solution:

	def lcs(self, x, y, s1, s2):
		dp = [[0] * (x + 1) for _ in range(y + 1)]
		for r in range(1, y + 1):
			for c in range(1, x + 1):
				if s1[c - 1] == s2[r - 1]:
					dp[r][c] = 1 + dp[r - 1][c - 1]
				else:
					dp[r][c] = max(dp[r - 1][c], dp[r][c - 1])
		return dp[-1][-1]


class Solution:

	def lcs(self, x, y, s1, s2):

		def go(ind1, ind2):
			if ind1 == x or ind2 == y:
				return 0
			if dp[ind1][ind2] != -1:
				return dp[ind1][ind2]
			c1 = 0
			if s1[ind1] == s2[ind2]:
				c1 = 1 + go(ind1 + 1, ind2 + 1)
			c2 = go(ind1 + 1, ind2)
			c3 = go(ind1, ind2 + 1)
			ans = max(c1, c2, c3)
			dp[ind1][ind2] = ans
			return ans
		dp = []
		for i in range(x):
			q = []
			for j in range(y):
				q.append(-1)
			dp.append(q)
		return go(0, 0)


class Solution:

	def lcs(self, x, y, s1, s2):
		T = [[-1 for i in range(y + 1)] for i in range(x + 1)]
		return helper(x, y, s1, s2, T)

def helper(x, y, s1, s2, T):
	if x == 0 or y == 0:
		return 0
	if T[x][y] != -1:
		return T[x][y]
	if s1[x - 1] == s2[y - 1]:
		T[x][y] = 1 + helper(x - 1, y - 1, s1, s2, T)
		return T[x][y]
	else:
		T[x][y] = max(helper(x, y - 1, s1, s2, T), helper(x - 1, y, s1, s2, T))
		return T[x][y]


class Solution:

	def subseq(self, i, j, s1, s2, dp):
		if i < 0 or j < 0:
			return 0
		if dp[i][j] != -1:
			return dp[i][j]
		if s1[i] == s2[j]:
			dp[i][j] = 1 + self.subseq(i - 1, j - 1, s1, s2, dp)
		else:
			sub1 = self.subseq(i - 1, j, s1, s2, dp)
			sub2 = self.subseq(i, j - 1, s1, s2, dp)
			dp[i][j] = 0 + max(sub1, sub2)
		return dp[i][j]

	def lcs(self, x, y, s1, s2):
		dp = [[-1 for i in range(y)] for j in range(x)]
		return self.subseq(x - 1, y - 1, s1, s2, dp)


import numpy as np

class Solution:

	def rec_sol(self, x, y, s1, s2):
		if x < 0 or y < 0:
			return 0
		if s1[x] == s2[y]:
			return 1 + self.rec_sol(x - 1, y - 1, s1, s2)
		else:
			return max(self.rec_sol(x - 1, y, s1, s2), self.rec_sol(x, y - 1, s1, s2))

	def dp_sol(self, x, y, s1, s2):
		dp = np.array([[0] * y] * x)
		for i in range(x):
			for j in range(y):
				if s1[i] == s2[j]:
					if i - 1 >= 0 and j - 1 >= 0:
						dp[i][j] = 1 + dp[i - 1][j - 1]
					else:
						dp[i][j] = 1
				else:
					if i - 1 >= 0:
						dp[i][j] = max(dp[i][j], dp[i - 1][j])
					if j - 1 >= 0:
						dp[i][j] = max(dp[i][j], dp[i][j - 1])
		return dp[x - 1][y - 1]

	def lcs(self, x, y, s1, s2):
		return self.dp_sol(x, y, s1, s2)


class Solution:

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


class Solution:

	def lcs(self, x, y, s1, s2):
		dp = [[-1 for j in range(y)] for i in range(x)]
		return self.func(x, y, s1, s2, 0, 0, dp)

	def func(self, x, y, s1, s2, i, j, dp):
		if i == x:
			return 0
		if j == y:
			return 0
		if dp[i][j] != -1:
			return dp[i][j]
		count = 0
		if s1[i] == s2[j]:
			count = 1 + self.func(x, y, s1, s2, i + 1, j + 1, dp)
		elif s1[i] != s2[j]:
			count = max(self.func(x, y, s1, s2, i, j + 1, dp), self.func(x, y, s1, s2, i + 1, j, dp))
		dp[i][j] = count
		return count


def max1(dp, x, y):
	res = 0
	for i in range(x + 1):
		for j in range(y + 1):
			res = max(res, dp[i][j])
	return res

def helper(dp, s1, s2, x, y):
	if x == 0 or y == 0:
		return 0
	if dp[x][y] != -1:
		return dp[x][y]
	elif s1[x - 1] == s2[y - 1]:
		dp[x][y] = 1 + helper(dp, s1, s2, x - 1, y - 1)
		return dp[x][y]
	else:
		dp[x][y] = max(helper(dp, s1, s2, x - 1, y), helper(dp, s1, s2, x, y - 1))
		return dp[x][y]

class Solution:

	def lcs(self, x, y, s1, s2):
		dp = [[-1 for _ in range(y + 1)] for j in range(x + 1)]
		helper(dp, s1, s2, x, y)
		return dp[x][y]


class Solution:

	def lcs(self, n, m, x, y):
		t = [[-1 for i in range(m + 1)] for i in range(n + 1)]
		for i in range(n + 1):
			for j in range(m + 1):
				if i == 0 or j == 0:
					t[i][j] = 0
		for i in range(1, n + 1):
			for j in range(1, m + 1):
				if x[i - 1] == y[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[i][j]


class Solution:

	def ls(self, x, y, s1, s2, dp):
		if x == 0 or y == 0:
			return 0
		if dp[x][y] != -1:
			return dp[x][y]
		if s1[x - 1] == s2[y - 1]:
			dp[x][y] = 1 + self.ls(x - 1, y - 1, s1, s2, dp)
			return dp[x][y]
		else:
			dp[x][y] = max(self.ls(x - 1, y, s1, s2, dp), self.ls(x, y - 1, s1, s2, dp))
			return dp[x][y]

	def lcs(self, x, y, s1, s2):
		dp = [[-1 for _ in range(y + 1)] for _ in range(x + 1)]
		return self.ls(x, y, s1, s2, dp)


class Solution:

	def lcs(self, x, y, s1, s2):
		dp = [[-1] * (y + 1) for i in range(x + 1)]

		def reccur(i, j):
			if i < 0 or j < 0:
				return 0
			if dp[i][j] != -1:
				return dp[i][j]
			if s1[i] == s2[j]:
				dp[i][j] = 1 + reccur(i - 1, j - 1)
				return dp[i][j]
			dp[i][j] = max(reccur(i - 1, j), reccur(i, j - 1))
			return dp[i][j]
		return reccur(x - 1, y - 1)


class Solution:

	def lcs(self, x, y, str1, str2):
		dp = []
		p = []
		for i in range(len(str1) + 1):
			for j in range(len(str2) + 1):
				p.append(0)
			dp.append(p)
			p = []
		for i in range(len(str1) + 1):
			for j in range(len(str2) + 1):
				if i == 0 or j == 0:
					dp[i][j] = 0
				elif str1[i - 1] == str2[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[len(str1)][len(str2)]


class Solution:

	def lcs(self, x, y, s1, s2):
		m = len(s1)
		n = len(s2)
		mat = [[0 for j in range(n + 1)] for i in range(m + 1)]
		for i in range(len(s2)):
			mat[0][i] = 0
		for j in range(len(s1)):
			mat[j][0] = 0
		for i in range(1, m + 1):
			for j in range(1, n + 1):
				if s1[i - 1] == s2[j - 1]:
					mat[i][j] = mat[i - 1][j - 1] + 1
				else:
					mat[i][j] = 0 + max(mat[i - 1][j], mat[i][j - 1])
		return mat[m][n]


class Solution:

	def lcs(self, x, y, s1, s2):

		def LCS(s1, s2, x, y):
			nonlocal t
			if x == 0 or y == 0:
				return 0
			if t[x][y] != -1:
				return t[x][y]
			if s1[x - 1] == s2[y - 1]:
				t[x][y] = 1 + LCS(s1, s2, x - 1, y - 1)
				return t[x][y]
			else:
				t[x][y] = max(LCS(s1, s2, x, y - 1), LCS(s1, s2, x - 1, y))
				return t[x][y]
		t = [[-1 for j in range(y + 1)] for i in range(x + 1)]
		return LCS(s1, s2, x, y)


class Solution:

	def lcs(self, x, y, s1, s2):
		dp = [[-1 for i in range(y + 1)] for j in range(x + 1)]
		return self.solve(x, y, s1, s2, dp)

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


class Solution:

	def lcs(self, x, y, s1, s2):
		n1 = len(s1)
		n2 = len(s2)
		dp = [0 for j in range(n2 + 1)]
		tmp = [0 for i in range(n2 + 1)]
		for i in range(1, n1 + 1):
			for j in range(1, n2 + 1):
				if s1[i - 1] == s2[j - 1]:
					dp[j] = tmp[j - 1] + 1
				else:
					dp[j] = max(dp[j - 1], tmp[j])
			tmp = dp
			dp = [0 for j in range(n2 + 1)]
		return tmp[-1]


from functools import lru_cache

class Solution:

	def lcs(self, x, y, s1, s2):
		dp = [[0 for _ in range(y + 1)] for _ in range(x + 1)]
		for i in range(1, x + 1):
			for j in range(1, y + 1):
				if s1[i - 1] == s2[j - 1]:
					dp[i][j] = 1 + dp[i - 1][j - 1]
				else:
					dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
		return dp[-1][-1]


from functools import lru_cache

class Solution:

	def lcs(self, x, y, s1, s2):

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


class Solution:

	def lcs(self, x, y, s1, s2):
		if x == 0 or y == 0:
			return 0
		self.arr = [[0] * (y + 1) for i in range(x + 1)]
		for i in range(x + 1):
			for j in range(y + 1):
				if i == 0 or j == 0:
					continue
				if s1[i - 1] == s2[j - 1]:
					self.arr[i][j] = 1 + self.arr[i - 1][j - 1]
				else:
					self.arr[i][j] = max(self.arr[i - 1][j], self.arr[i][j - 1])
		return self.arr[i][j]


class Solution:

	def solve(self, x, y, s1, s2, i, j):
		if i == x or j == y:
			return 0
		if s1[i] == s2[j]:
			return 1 + self.solve(x, y, s1, s2, i + 1, j + 1)
		else:
			return max(self.solve(x, y, s1, s2, i + 1, j), self.solve(x, y, s1, s2, i, j + 1))

	def solve_memo(self, x, y, s1, s2, i, j, F):
		if i == x or j == y:
			return 0
		if F[i][j] != -1:
			return F[i][j]
		if s1[i] == s2[j]:
			F[i][j] = 1 + self.solve_memo(x, y, s1, s2, i + 1, j + 1, F)
		else:
			F[i][j] = max(self.solve_memo(x, y, s1, s2, i + 1, j, F), self.solve_memo(x, y, s1, s2, i, j + 1, F))
		return F[i][j]

	def solve_tab(self, x, y, s1, s2):
		F = [[0 for _ in range(y + 1)] for _ in range(x + 1)]
		for i in range(x - 1, -1, -1):
			for j in range(y - 1, -1, -1):
				if s1[i] == s2[j]:
					F[i][j] = 1 + F[i + 1][j + 1]
				else:
					F[i][j] = max(F[i + 1][j], F[i][j + 1])
		return F[0][0]

	def solve_tab2(self, x, y, s1, s2):
		curr = [0 for _ in range(y + 1)]
		nextt = [0 for _ in range(y + 1)]
		for i in range(x - 1, -1, -1):
			for j in range(y - 1, -1, -1):
				if s1[i] == s2[j]:
					curr[j] = 1 + nextt[j + 1]
				else:
					curr[j] = max(nextt[j], curr[j + 1])
			nextt = curr[:]
		return nextt[0]

	def lcs(self, x, y, s1, s2):
		return self.solve_tab2(x, y, s1, s2)


class Solution:

	def lcs(self, x, y, s1, s2):
		(n, m) = (len(s1), len(s2))
		l = [[0] * (m + 1) for i in range(n + 1)]
		for r in range(1, n + 1):
			for c in range(1, m + 1):
				if s1[r - 1] == s2[c - 1]:
					l[r][c] = 1 + l[r - 1][c - 1]
				else:
					l[r][c] = max(l[r - 1][c], l[r][c - 1])
		return l[-1][-1]


class Solution:

	def lcs(self, n, m, S1, S2):
		dp = [[0 for i in range(m + 1)] for j in range(n + 1)]
		for i in range(1, n + 1):
			for j in range(1, m + 1):
				if S1[i - 1] == S2[j - 1]:
					dp[i][j] = 1 + dp[i - 1][j - 1]
				else:
					dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
		return dp[n][m]


class Solution:

	def lcs(self, x, y, s1, s2):
		stateMap = [[0 for i in range(y + 1)] for _ in range(x + 1)]
		for r in range(1, x + 1):
			for c in range(1, y + 1):
				stateMap[r][c] = max(stateMap[r - 1][c], stateMap[r][c - 1])
				if s1[r - 1] == s2[c - 1]:
					stateMap[r][c] = max(stateMap[r][c], 1 + stateMap[r - 1][c - 1])
		return stateMap[r][c]


class Solution:

	def lcs(self, x, y, s1, s2):
		memo = {}

		def recurse(i, j):
			key = (i, j)
			if key in memo:
				return memo[key]
			elif i == x or j == y:
				memo[key] = 0
			elif s1[i] == s2[j]:
				memo[key] = 1 + recurse(i + 1, j + 1)
			else:
				option1 = recurse(i + 1, j)
				option2 = recurse(i, j + 1)
				memo[key] = max(option1, option2)
			return memo[key]
		return recurse(0, 0)


class Solution:

	def lcs(self, x, y, str1, str2):
		dp = {}

		def solve(s1, s2, m, n):
			if n == 0 or m == 0:
				return 0
			elif (m, n) in dp:
				return dp[m, n]
			else:
				if s1[m - 1] == s2[n - 1]:
					c = 1 + solve(s1, s2, m - 1, n - 1)
				else:
					c1 = solve(s1, s2, m - 1, n)
					c2 = solve(s1, s2, m, n - 1)
					c = max(c1, c2)
				dp[m, n] = c
				return c
		return solve(str1, str2, x, y)