Given two string X and Y of length N and M respectively. The task is to find the length of the longest subsequence of string X which is a substring in sequence Y.
Example 1:
Input:
N = 4, M = 8
X = "abcd"
Y = "bacdbdcd"
Output: 3
Explanation: "acd" is the longest subsequence
             from string X present as a
             substring in string Y.
Example 2:
Input:
N = 1, M = 1
X = 'a'
Y = 'a'
Output: 1
Explanation: 'a' is the answer.
Your Task:
You don't need to read input or print anything. Your task is to complete the function maxSubsequenceSubstring() which takes 4 arguments(string X, string Y, N and M) and returns the answer. 
Expected Time Complexity: O(N*M).
Expected Auxiliary Space: O(N*M).
Constraints:
1<= N, M <=10^{3}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: String algorithms

Dynamic programming

Data structures

Starter code: #User function Template for python3

class Solution:

    def maxSubsequenceSubstring(self, X, Y, N, M):
        # code here

Solutions:
class Solution:

	def maxSubsequenceSubstring(self, X, Y, N, M):
		m = len(X)
		n = len(Y)
		dp = [[0 for _ in range(n + 1)] for _ in range(m + 1)]
		res = 0
		for i in range(1, m + 1):
			for j in range(1, n + 1):
				if X[i - 1] == Y[j - 1]:
					dp[i][j] = 1 + dp[i - 1][j - 1]
					res = max(res, dp[i][j])
				else:
					dp[i][j] = dp[i - 1][j]
		return res


class Solution:

	def maxSubsequenceSubstring(self, X, Y, N, M):
		dp = [[0 for j in range(len(X) + 1)] for i in range(len(Y) + 1)]
		c = 0
		for i in range(len(Y) - 1, -1, -1):
			for j in range(len(X) - 1, -1, -1):
				if Y[i] == X[j]:
					dp[i][j] = 1 + dp[i + 1][j + 1]
				else:
					dp[i][j] = dp[i][j + 1]
				c = max(c, dp[i][j])
		return c


import numpy as np

class Solution:

	def maxSubsequenceSubstring(self, X, Y, N, M):
		t = [[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 X[i - 1] == Y[j - 1]:
					t[i][j] = 1 + t[i - 1][j - 1]
				else:
					t[i][j] = t[i - 1][j]
		return np.amax(t)


class Solution:

	def maxSubsequenceSubstring(self, x, y, n, m):
		dp = [[0 for j in range(m + 1)] for i in range(n + 1)]
		for j in range(m + 1):
			dp[0][j] = 0
		for i in range(n + 1):
			dp[i][0] = 0
		for i in range(1, n + 1):
			for j in range(1, m + 1):
				if x[i - 1] == y[j - 1]:
					dp[i][j] = 1 + dp[i - 1][j - 1]
				else:
					dp[i][j] = dp[i - 1][j]
		maxlen = 0
		for j in range(1, m + 1):
			maxlen = max(maxlen, dp[n][j])
		return maxlen


class Solution:

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


class Solution:

	def maxSubsequenceSubstring(self, X, Y, N, M):
		dp = [[0 for j in range(len(Y) + 1)] for i in range(len(X) + 1)]
		result = 0
		for i in range(len(X) - 1, -1, -1):
			for j in range(len(Y) - 1, -1, -1):
				if X[i] == Y[j]:
					dp[i][j] = 1 + dp[i + 1][j + 1]
				else:
					dp[i][j] = dp[i + 1][j]
				result = max(result, dp[i][j])
		return result
		if not X or not Y:
			return 0
		dp = [[0] * (Y + 1) for _ in range(X + 1)]
		result = 0
		for i in range(X - 1, -1, -1):
			for j in range(Y - 1, -1, -1):
				if x[i] == y[j]:
					dp[i][j] = dp[i + 1][j + 1] + 1
				else:
					dp[i][j] = dp[i + 1][j]
				result = max(result, dp[i][j])
		return result


class Solution:

	def maxSubsequenceSubstring(self, a, b, N, M):

		def func(subsequence: str, substring: str, i: int, j: int):
			if i == len(subsequence) or j == len(substring):
				return 0
			if subsequence[i] == substring[j]:
				return 1 + func(subsequence, substring, i + 1, j + 1)
			else:
				return func(subsequence, substring, i + 1, j)
		max_len = 0
		for i in range(len(b)):
			max_len = max(max_len, func(a, b, 0, i))
		return max_len


class Solution:

	def maxSubsequenceSubstring(self, X, Y, N, M):

		def dp(n, m):
			if n == 0 or m == 0:
				return 0
			if X[n - 1] == Y[m - 1]:
				return 1 + dp(n - 1, m - 1)
			else:
				return dp(n - 1, m)
		maxLen = 0
		(n, m) = (N, M)
		for i in range(m + 1):
			maxLen = max(maxLen, dp(n, i))
		return maxLen


class Solution:

	def maxSubsequenceSubstring(self, x, y, n, m):

		def rec(x, y, n, m):
			if n == 0 or m == 0:
				return 0
			if x[n - 1] == y[m - 1]:
				return 1 + rec(x, y, n - 1, m - 1)
			else:
				return rec(x, y, n - 1, m)
		max_len = 0
		for i in range(m + 1):
			max_len = max(max_len, rec(x, y, n, i))
		return max_len


class Solution:

	def maxSubsequenceSubstring(self, X, Y, N, M):
		d = {}

		def rec(i1, i2):
			if i1 == N or i2 == M:
				return 0
			tu = tuple([i1, i2])
			if tu in d:
				return d[tu]
			if X[i1] == Y[i2]:
				d[tu] = 1 + rec(i1 + 1, i2 + 1)
			else:
				d[tu] = rec(i1 + 1, i2)
			return d[tu]
		ans = 0
		for i in range(M):
			ans = max(ans, rec(0, i))
		return ans


class Solution:

	def maxSubsequenceSubstring(self, X, Y, N, M):
		dp = [[0] * (N + 1) for _ in range(M + 1)]
		maxsubstring = 0
		for i in range(1, M + 1):
			for j in range(1, N + 1):
				if X[j - 1] == Y[i - 1]:
					dp[i][j] = dp[i - 1][j - 1] + 1
				else:
					dp[i][j] = dp[i][j - 1]
				maxsubstring = max(maxsubstring, dp[i][j])
		return maxsubstring


class Solution:

	def match(self, x, y, n, m, memo):
		if n == 0 or m == 0:
			return 0
		if memo[n][m] is not None:
			return memo[n][m]
		result = None
		if x[n - 1] == y[m - 1]:
			result = 1 + self.match(x, y, n - 1, m - 1, memo)
		else:
			result = self.match(x, y, n - 1, m, memo)
		memo[n][m] = result
		return result

	def maxSubsequenceSubstring(self, x, y, n, m):
		memo = [[None for _ in range(m + 1)] for __ in range(n + 1)]
		_max = 0
		for end in range(m, -1, -1):
			_max = max(_max, self.match(x, y, n, end, memo))
		return _max


class Solution:

	def maxSubsequenceSubstring(self, X, Y, N, M):
		if N == 0 or M == 0:
			return 0
		max_length = 0
		for i in range(M):
			curr_length = 0
			idx = i
			for j in range(N):
				if X[j] == Y[idx]:
					idx += 1
					curr_length += 1
					if idx == M:
						break
			max_length = max(curr_length, max_length)
		return max_length


import sys

class Solution:

	def maxSubsequenceSubstring(self, x, y, n, m):
		dp = [[0 for i in range(n + 1)] for i in range(m + 1)]
		for i in range(1, m + 1):
			for j in range(1, n + 1):
				if x[j - 1] == y[i - 1]:
					dp[i][j] = 1 + dp[i - 1][j - 1]
				else:
					dp[i][j] = dp[i][j - 1]
		ans = 0
		for i in range(1, m + 1):
			ans = max(ans, dp[i][n])
		return ans


class Solution:

	def maxSubsequenceSubstring(self, x, y, n, m):
		MAX = 1000
		dp = [[0 for i in range(len(x) + 1)] for i in range(len(y) + 1)]
		for i in range(1, m + 1):
			for j in range(1, n + 1):
				if x[j - 1] == y[i - 1]:
					dp[i][j] = 1 + dp[i - 1][j - 1]
				else:
					dp[i][j] = dp[i][j - 1]
		ans = 0
		for i in range(1, m + 1):
			ans = max(ans, dp[i][n])
		return ans


class Solution:

	def maxSubsequenceSubstring(self, X, Y, N, M):
		res = 0
		for i in range(M):
			t = i
			curr = 0
			j = 0
			while j < N and t < M:
				if X[j] == Y[t]:
					t += 1
					curr += 1
				j += 1
			res = max(res, curr)
		return res


class Solution:

	def maxSubsequenceSubstring(self, x, y, n, m):
		dp = [[0 for i in range(n + 1)] for i in range(m + 1)]
		for i in range(1, m + 1):
			for j in range(1, n + 1):
				if x[j - 1] == y[i - 1]:
					dp[i][j] = 1 + dp[i - 1][j - 1]
				else:
					dp[i][j] = dp[i][j - 1]
		biggest = 0
		for (i, r) in enumerate(dp):
			biggest = max(biggest, max(r))
		return biggest


class Solution:

	def maxSubsequenceSubstring(self, text1, text2, N, M):
		dp = [[0] * (M + 1) for _ in range(2)]
		b = 1
		ans = 0
		for i in range(1, N + 1):
			b ^= 1
			for j in range(1, M + 1):
				if text1[i - 1] == text2[j - 1]:
					dp[b][j] = 1 + dp[1 - b][j - 1]
					ans = max(dp[b][j], ans)
				else:
					dp[b][j] = dp[1 - b][j]
		return ans


def solve(s1, s2, i, j):
	if i >= len(s1) or j >= len(s2):
		return 0
	if s1[i] == s2[j]:
		return 1 + solve(s1, s2, i + 1, j + 1)
	return solve(s1, s2, i + 1, j)

class Solution:

	def maxSubsequenceSubstring(self, X, Y, N, M):
		res = 0
		for i in range(M):
			res = max(res, solve(X, Y, 0, i))
		return res


class Solution:

	def maxSubsequenceSubstring(self, X, Y, N, M):
		t = [[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 X[i - 1] == Y[j - 1]:
					t[i][j] = t[i - 1][j - 1] + 1
				else:
					t[i][j] = t[i - 1][j]
		m = t[-1][-1]
		for i in range(N + 1):
			for j in range(M + 1):
				if t[i][j] > m:
					m = t[i][j]
		return m


import math
import os
import random
import re
import sys

class Solution:

	def maxSubsequenceSubstring(self, x, y, n, m):
		dp = [[0 for i in range(n + 1)] for i in range(m + 1)]
		for i in range(1, m + 1):
			for j in range(1, n + 1):
				if x[j - 1] == y[i - 1]:
					dp[i][j] = 1 + dp[i - 1][j - 1]
				else:
					dp[i][j] = dp[i][j - 1]
		maxLength = 0
		for i in range(1, m + 1):
			maxLength = max(maxLength, dp[i][n])
		return maxLength


class Solution:

	def maxSubsequenceSubstring(self, x, y, n, m):
		ans = 0

		def foo(x, y, n, m):
			if n == 0 or m == 0:
				return 0
			if x[n - 1] == y[m - 1]:
				return 1 + foo(x, y, n - 1, m - 1)
			else:
				return foo(x, y, n - 1, m)
		for i in range(m, -1, -1):
			ans = max(ans, foo(x, y, n, i))
		return ans


class Solution:

	def maxSubsequenceSubstring(self, a, b, n, m):
		ans = 0
		for i in range(m):
			j = i
			k = 0
			while k < n and j < m:
				if b[j] == a[k]:
					j += 1
				k += 1
			ans = max(ans, j - i)
		return ans


class Solution:

	def maxSubsequenceSubstring(self, s1, s2, N, M):
		table = [[-1 for i in range(M + 1)] for j in range(N + 1)]
		ans = [0]
		for x in range(0, N + 1):
			for y in range(0, M + 1):
				if x == 0 or y == 0:
					table[x][y] = 0
					continue
				if s1[x - 1] == s2[y - 1]:
					table[x][y] = table[x - 1][y - 1] + 1
				else:
					table[x][y] = table[x - 1][y]
				if table[x][y] > ans[0]:
					ans[0] = table[x][y]
		return ans[0]


class Solution:

	def maxSubsequenceSubstring(self, X, Y, N, M):
		ma = 0
		for i in range(M):
			k = i
			j = 0
			req = 0
			while j < N and k < M:
				if X[j] == Y[k]:
					k = k + 1
					req = req + 1
				j = j + 1
			ma = max(ma, req)
		return ma