Given two strings X and Y of lengths m and n respectively, find the length of the smallest string which has both, X and Y as its sub-sequences.
Note: X and Y can have both uppercase and lowercase letters.
Example 1
Input:
X = abcd, Y = xycd
Output: 6
Explanation: Shortest Common Supersequence
would be abxycd which is of length 6 and
has both the strings as its subsequences.
Example 2
Input:
X = efgh, Y = jghi
Output: 6
Explanation: Shortest Common Supersequence
would be ejfghi which is of length 6 and
has both the strings as its subsequences.
Your Task:
Complete shortestCommonSupersequence() function that takes X, Y, m, and n as arguments and returns the length of the required string.
Expected Time Complexity: O(Length(X) * Length(Y)).
Expected Auxiliary Space: O(Length(X) * Length(Y)).
Constraints:
1<= |X|, |Y| <= 100

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: String algorithms

Dynamic programming

Data structures

Starter code: #User function Template for python3

class Solution:
    
    #Function to find length of shortest common supersequence of two strings.
    def shortestCommonSupersequence(self, X, Y, m, n):
        
         #code here

Solutions:
class Solution:

	def shortestCommonSupersequence(self, X, Y, m, n):
		dp = [[0 for k in range(len(Y) + 1)] for j in range(len(X) + 1)]
		str1 = ''
		for i in range(1, len(X) + 1):
			for j in range(1, len(Y) + 1):
				if X[i - 1] == Y[j - 1]:
					dp[i][j] = 1 + dp[i - 1][j - 1]
				elif i == 0 and j == 0:
					dp[i][j] = 0
				else:
					dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
		return len(Y) + (len(X) - dp[-1][-1])


class Solution:

	def shortestCommonSupersequence(self, X, Y, m, n):
		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[i - 1] == Y[j - 1]:
					dp[i][j] = 1 + dp[i - 1][j - 1]
				else:
					dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
		lcs = dp[m][n]
		return m + n - lcs


class Solution:

	def lcs(self, s1: str, s2: str) -> int:
		dp = [[0] * (len(s2) + 1) for j in range(len(s1) + 1)]
		for i in range(1, len(s1) + 1):
			for j in range(1, len(s2) + 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]

	def shortestCommonSupersequence(self, X, Y, m, n):
		return m + n - self.lcs(X, Y)


class Solution:

	def shortestCommonSupersequence(self, X, Y, m, n):
		t = [[0 for j 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[i - 1] == Y[j - 1]:
					t[i][j] = 1 + t[i - 1][j - 1]
				else:
					t[i][j] = max(t[i - 1][j], t[i][j - 1])
		Lcs = t[m][n]
		return m + n - Lcs


class Solution:

	def shortestCommonSupersequence(self, X, Y, m, n):

		def LCS(x, y, m, n):
			t = [[-1] * (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:
						t[i][j] == 0
			for i in range(1, m + 1):
				for j in range(1, n + 1):
					if x[i - 1] == y[j - 1]:
						t[i][j] = 1 + t[i - 1][j - 1]
					else:
						t[i][j] = max(t[i - 1][j], t[i][j - 1])
			return t[m][n]
		t = LCS(X, Y, m, n)
		return m + n - t - 1


class Solution:

	def shortestCommonSupersequence(self, s1, s2, x, y):
		x = len(s1)
		y = len(s2)
		dp = [[-1 for i in range(y)] for j in range(x)]

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


class Solution:

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

	def shortestCommonSupersequence(self, X, Y, m, n):
		lcs_len = self.lcs(X, Y, m, n)
		return m + n - lcs_len


class Solution:

	def shortestCommonSupersequence(self, X, Y, m, n):
		arr = [[0 for j in range(n + 1)] for i in range(m + 1)]
		for j in range(n + 1):
			arr[0][j] = j
		for i in range(m + 1):
			arr[i][0] = i
		for i in range(1, m + 1):
			for j in range(1, n + 1):
				if X[i - 1] == Y[j - 1]:
					arr[i][j] = arr[i - 1][j - 1] + 1
				else:
					arr[i][j] = min(arr[i - 1][j], arr[i][j - 1]) + 1
		return arr[m][n]


class Solution:

	def shortestCommonSupersequence(self, X, Y, n, m):
		res = [[0 for _ in range(m + 1)] for x 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]:
					res[i][j] = 1 + res[i - 1][j - 1]
				else:
					res[i][j] = max(res[i - 1][j], res[i][j - 1])
		pk = res[n][m]
		ans = pk + (n - pk) + (m - pk)
		return ans


class Solution:

	def shortestCommonSupersequence(self, X, Y, m, n):
		str1 = X + Y
		str = len(str1)
		n = len(X)
		m = len(Y)
		str2 = self.lcs(n, m, X, Y)
		return str - str2

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


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 shortestCommonSupersequence(self, X, Y, m, n):
		dp = [[-1 for _ in range(n + 1)] for _ in range(m + 1)]
		return m + n - self.ls(m, n, X, Y, dp)


class Solution:

	def shortestCommonSupersequence(self, X, Y, m, n):
		return m + n - self.scf(X, Y, m, n)

	def scf(self, X, Y, m, n):
		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 X[i - 1] == Y[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 shortestCommonSupersequence(self, X, Y, m, n):
		dp = [[-1] * (n + 1) for i in range(m + 1)]

		def lcs(x, y, n, m):
			if n == 0 or m == 0:
				return 0
			if dp[n][m] != -1:
				return dp[n][m]
			if x[n - 1] == y[m - 1]:
				dp[n][m] = 1 + lcs(x, y, n - 1, m - 1)
			else:
				dp[n][m] = max(lcs(x, y, n - 1, m), lcs(x, y, n, m - 1))
			return dp[n][m]
		ans = lcs(X, Y, m, n)
		return m + n - ans


class Solution:

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

	def shortestCommonSupersequence(self, X, Y, m, n):
		str1 = X
		str2 = Y
		m = len(str1)
		n = len(str2)
		dp = []
		for i in range(m + 1):
			dp.append([])
			for j in range(n + 1):
				dp[i].append(-1)
		common = self.lcs(str1, str2, dp, m, n)
		return len(str1) + len(str2) - common


class Solution:

	def shortestCommonSupersequence(self, X, Y, m, n):
		dp = [[0] * (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:
					pass
				elif X[i - 1] == Y[j - 1]:
					dp[i][j] = 1 + dp[i - 1][j - 1]
				else:
					dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
		lcs = dp[m][n]
		ans = m + n - lcs
		return ans


class Solution:

	def shortestCommonSupersequence(self, s1, s2, x, y):
		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][j - 1], dp[i - 1][j])
		lcs = dp[x][y]
		result = lcs + (x - lcs) + (y - lcs)
		return result


class Solution:
	dp = []

	def gen(self, x, y, m, n):
		if m < 0 or n < 0:
			return abs(m - n)
		p = 999999
		if self.dp[m][n] != -1:
			return self.dp[m][n]
		if x[m] == y[n]:
			p = self.gen(x, y, m - 1, n - 1) + 1
		q = self.gen(x, y, m - 1, n) + 1
		r = self.gen(x, y, m, n - 1) + 1
		self.dp[m][n] = min(p, q, r)
		return min(p, q, r)

	def shortestCommonSupersequence(self, X, Y, m, n):
		self.dp = []
		for i in range(m):
			b = []
			for j in range(n):
				b.append(-1)
			self.dp.append(b)
		return self.gen(X, Y, m - 1, n - 1)


class Solution:

	def shortestCommonSupersequence(self, m, n, X, Y):

		def lcs(x, y, s1, s2):
			dp = [[0 for i in range(x + 1)] for j in range(y + 1)]
			for i in range(y):
				for j in range(x):
					if s1[j] == s2[i]:
						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[-1][-1]
		return X + Y - lcs(X, Y, m, n)


class Solution:

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

		def find(x, y, s1, s2, dp):
			if x >= len(s1):
				return 0
			if y >= len(s2):
				return 0
			if dp[x][y] != -1:
				return dp[x][y]
			ans = 0
			if s1[x] == s2[y]:
				ans += 1 + find(x + 1, y + 1, s1, s2, dp)
			else:
				ans += max(find(x + 1, y, s1, s2, dp), find(x, y + 1, s1, s2, dp))
			dp[x][y] = ans
			return dp[x][y]
		dp = [[-1 for _ in range(y)] for i in range(x)]
		return x + y - find(0, 0, s1, s2, dp)


class Solution:

	def shortestCommonSupersequence(self, s1, s2, x, y):
		dp = [[0] * (y + 1) for _ in range(x + 1)]
		for i in range(x + 1):
			for j in range(y + 1):
				(m, n) = (i, j)
				if m == 0 or n == 0:
					pass
				elif s1[m - 1] == s2[n - 1]:
					dp[i][j] = 1 + dp[i - 1][j - 1]
				else:
					c1 = dp[i - 1][j]
					c2 = dp[i][j - 1]
					dp[i][j] = max(c1, c2)
		c = dp[x][y]
		return x + y - c


class Solution:

	def shortestCommonSupersequence(self, str1, str2, m, n):
		m = len(str1)
		n = len(str2)
		dp = {}

		def f(i, j):
			if (i, j) in dp:
				return dp[i, j]
			if i < 0 and j < 0:
				return 0
			if i >= 0 and j < 0:
				return i + 1
			if j >= 0 and i < 0:
				return j + 1
			if str1[i] == str2[j]:
				dp[i, j] = 1 + f(i - 1, j - 1)
				return dp[i, j]
			else:
				dp[i, j] = 1 + min(f(i - 1, j), f(i, j - 1))
				return dp[i, j]
		return f(m - 1, n - 1)


class Solution:

	def shortestCommonSupersequence(self, X, Y, m, n):
		dp = [[0 for i in range(n + 1)] for j in range(m + 1)]
		res = 0
		ans = self.f(X, Y, m, n, dp)
		if n > m:
			res = m - ans
			return n + res
		else:
			res = n - ans
			return m + res

	def f(self, X, Y, m, n, dp):
		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]
				else:
					dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
		return dp[m][n]


class Solution:

	def shortestCommonSupersequence(self, X, Y, m, n):
		x = X
		y = Y
		dp = [[0] * (n + 1) for i in range(m + 1)]
		for i in range(m):
			dp[i][n] = m - i
		for j in range(n):
			dp[m][j] = n - j
		for i in range(m - 1, -1, -1):
			for j in range(n - 1, -1, -1):
				dp[i][j] = dp[i + 1][j + 1] + 1 if x[i] == y[j] else min(dp[i + 1][j], dp[i][j + 1]) + 1
		return dp[0][0]


class Solution:

	def shortestCommonSupersequence(self, X, Y, m, n):

		def longestcommonsequence(x, y, m, n):
			dp = [[0 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:
						dp[i][j] == 0
			for i in range(1, n + 1):
				for j in range(1, m + 1):
					if x[j - 1] == y[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[n][m]
		return len(X) + len(Y) - longestcommonsequence(X, Y, m, n)


class Solution:

	def shortestCommonSupersequence(self, s1, s2, m, n):
		dp = [[-1] * (n + 1) for i in range(m + 1)]

		def solve(i, j, s1, s2):
			if i < 0 or j < 0:
				return 0
			ans = 0
			if dp[i][j] != -1:
				return dp[i][j]
			if s1[i] == s2[j]:
				ans = 1 + solve(i - 1, j - 1, s1, s2)
			else:
				ans = max(solve(i - 1, j, s1, s2), solve(i, j - 1, s1, s2))
			dp[i][j] = ans
			return ans
		lcs = solve(m - 1, n - 1, s1, s2)
		return m - lcs + n


class Solution:

	def shortestCommonSupersequence(self, X, Y, m, n):
		res = [[0 for y in range(n + 1)] for x in range(m + 1)]
		for i in range(m):
			for j in range(n):
				if X[i] == Y[j]:
					res[i + 1][j + 1] = 1 + res[i][j]
				else:
					res[i + 1][j + 1] = max(res[i + 1][j], res[i][j + 1])
		return m + n - res[-1][-1]


class Solution:

	def shortestCommonSupersequence(self, X, Y, m, n):
		dp = [[-1] * (n + 1) for i in range(m + 1)]
		for i in range(m + 1):
			dp[i][0] = 0
		for j in range(n + 1):
			dp[0][j] = 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]
				else:
					dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
		i = m
		j = n
		charstr = ''
		while i > 0 and j > 0:
			if X[i - 1] == Y[j - 1]:
				charstr += X[i - 1]
				i -= 1
				j -= 1
			elif dp[i - 1][j] > dp[i][j - 1]:
				charstr += X[i - 1]
				i -= 1
			else:
				charstr += Y[j - 1]
				j -= 1
		while i > 0:
			charstr += X[i - 1]
			i -= 1
		while j > 0:
			charstr += Y[j - 1]
			j -= 1
		return m + n - dp[m][n]


class Solution:

	def shortestCommonSupersequence(self, X, Y, m, n):
		t = [[-1 for i in range(n + 1)] for _ in range(m + 1)]

		def lcs(X, Y, m, n):
			for i in range(m + 1):
				for j in range(n + 1):
					if i == 0 or j == 0:
						t[i][j] = 0
			for i in range(1, m + 1):
				for j in range(1, n + 1):
					if X[i - 1] == Y[j - 1]:
						t[i][j] = 1 + t[i - 1][j - 1]
					else:
						t[i][j] = max(t[i - 1][j], t[i][j - 1])
			return t[m][n]
		l = lcs(X, Y, m, n)
		return m + n - l


class Solution:

	def shortestCommonSupersequence(self, X, Y, m, n):
		dp = [[0] * (n + 1) for _ in range(m + 1)]
		for i in range(1, m + 1):
			for j in range(1, n + 1):
				(c1, c2) = (X[i - 1], Y[j - 1])
				if c1 == c2:
					dp[i][j] = dp[i - 1][j - 1] + 1
				else:
					dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
		l = dp[m][n]
		return m + n - l


class Solution:

	def shortestCommonSupersequence(self, s1, s2, n, m):
		ans = ''
		dp = [[0 for j in range(m + 1)] for i in range(n + 1)]
		for ind1 in range(1, n + 1):
			for ind2 in range(1, m + 1):
				if s1[ind1 - 1] == s2[ind2 - 1]:
					dp[ind1][ind2] = 1 + dp[ind1 - 1][ind2 - 1]
				else:
					dp[ind1][ind2] = max(dp[ind1 - 1][ind2], dp[ind1][ind2 - 1])
		return n + m - dp[n][m]


class Solution:

	def shortestCommonSupersequence(self, X, Y, m, n):
		return m + n - self.lcs(X, Y, m, n)

	def lcs(self, X, Y, m, n):
		memory = [[0 for i in range(n + 1)] for j in range(m + 1)]
		for i in range(m + 1):
			for j in range(n + 1):
				if i == 0 or j == 0:
					memory[i][j] = 0
				elif X[i - 1] == Y[j - 1]:
					memory[i][j] = 1 + memory[i - 1][j - 1]
				else:
					memory[i][j] = max(memory[i - 1][j], memory[i][j - 1])
		return memory[m][n]


class Solution:

	def shortestCommonSupersequence(self, X, Y, m, n):
		L = [[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:
					L[i][j] = 0
				elif X[i - 1] == Y[j - 1]:
					L[i][j] = L[i - 1][j - 1] + 1
				else:
					L[i][j] = max(L[i - 1][j], L[i][j - 1])
		l = L[m][n]
		return m + n - l


class Solution:

	def common_sequence(self, X, Y, m, n):
		t = [[0 for _ in range(m + 1)] for _ in range(n + 1)]
		for i in range(n + 1):
			for j in range(m + 1):
				if i == 0 or j == 0:
					t[i][j] = 0
				elif X[j - 1] == Y[i - 1]:
					t[i][j] = t[i - 1][j - 1] + 1
				else:
					t[i][j] = max(t[i][j - 1], t[i - 1][j])
		return t[n][m]

	def shortestCommonSupersequence(self, X, Y, m, n):
		k = self.common_sequence(X, Y, m, n)
		return m + n - k


class Solution:

	def func(self, X, Y, m, n, t):
		for i in range(m + 1):
			for j in range(n + 1):
				if i == 0 or j == 0:
					t[i][j] = 0
		for i in range(1, m + 1):
			for j in range(1, n + 1):
				if X[i - 1] == Y[j - 1]:
					t[i][j] = 1 + t[i - 1][j - 1]
				else:
					t[i][j] = max(t[i - 1][j], t[i][j - 1])
		return t[m][n]

	def LCS(self, X, Y, m, n):
		t = [[0 for i in range(n + 1)] for i in range(m + 1)]
		c = self.func(X, Y, m, n, t)
		return c

	def shortestCommonSupersequence(self, X, Y, m, n):
		s = m + n - self.LCS(X, Y, m, n)
		return s


class Solution:

	def shortestCommonSupersequence(self, X, Y, m, n):
		n = len(X)
		m = len(Y)
		dp = [[0 for i in range(m + 1)] for i in range(n + 1)]
		for i in range(n + 1):
			dp[i][0] = 0
		for j in range(m + 1):
			dp[0][j] = 0
		for ind1 in range(1, n + 1):
			for ind2 in range(1, m + 1):
				if X[ind1 - 1] == Y[ind2 - 1]:
					dp[ind1][ind2] = 1 + dp[ind1 - 1][ind2 - 1]
				else:
					dp[ind1][ind2] = max(dp[ind1 - 1][ind2], dp[ind1][ind2 - 1])
		return n + m - dp[n][m]


class Solution:

	def shortestCommonSupersequence(self, s1, s2, m, n):
		dp = [[0 for i in range(n + 1)] for j in range(m + 1)]
		for i1 in range(1, m + 1):
			for i2 in range(1, n + 1):
				if s1[i1 - 1] == s2[i2 - 1]:
					dp[i1][i2] = 1 + dp[i1 - 1][i2 - 1]
				else:
					dp[i1][i2] = 0 + max(dp[i1 - 1][i2], dp[i1][i2 - 1])
		lcs = dp[m][n]
		mini = len(s1) - lcs + (len(s2) - lcs) + lcs
		return mini


class Solution:

	def shortestCommonSupersequence(self, X, Y, m, n):
		t = [[0] * (n + 1) for _ in range(m + 2)]
		for i in range(1, m + 1):
			for j in range(1, n + 1):
				if X[i - 1] == Y[j - 1]:
					t[i][j] = 1 + t[i - 1][j - 1]
				else:
					t[i][j] = max(t[i - 1][j], t[i][j - 1])
		result = m + n - t[m][n]
		return result


class Solution:

	def find_lcs(self, dp, txt1, txt2, m, n):
		if m == 0 or n == 0:
			return 0
		if dp[m][n] != -1:
			return dp[m][n]
		if txt1[m - 1] == txt2[n - 1]:
			dp[m][n] = 1 + self.find_lcs(dp, txt1, txt2, m - 1, n - 1)
			return dp[m][n]
		else:
			dp[m][n] = max(self.find_lcs(dp, txt1, txt2, m - 1, n), self.find_lcs(dp, txt1, txt2, m, n - 1))
			return dp[m][n]

	def shortestCommonSupersequence(self, X, Y, m, n):
		dp = [[-1 for i in range(n + 1)] for j in range(m + 1)]
		lcs = self.find_lcs(dp, X, Y, m, n)
		return m + n - lcs


class Solution:

	def shortestCommonSupersequence(self, X, Y, m, n):
		a = X
		b = Y
		n = len(a)
		m = len(b)
		S = [[0 for j in range(m)] for i in range(n)]
		S[0][0] = 1 if a[0] == b[0] else 0
		for i in range(1, n):
			if a[i] == b[0]:
				S[i][0] = 1
			else:
				S[i][0] = S[i - 1][0]
		for j in range(1, m):
			if a[0] == b[j]:
				S[0][j] = 1
			else:
				S[0][j] = S[0][j - 1]
		for i in range(1, n):
			for j in range(1, m):
				if a[i] == b[j]:
					S[i][j] = S[i - 1][j - 1] + 1
				else:
					S[i][j] = max(S[i - 1][j], S[i][j - 1])
		return n + m - S[n - 1][m - 1]


class Solution:

	def solve(self, X, Y, m, n, dp):
		ct = 0
		for a in range(1, m + 1):
			for b in range(1, n + 1):
				if X[a - 1] == Y[b - 1]:
					dp[a][b] = 1 + dp[a - 1][b - 1]
					ct = max(ct, dp[a][b])
				else:
					dp[a][b] = max(dp[a - 1][b], dp[a][b - 1])
					ct = max(ct, dp[a][b])
		return ct

	def shortestCommonSupersequence(self, X, Y, m, n):
		dp = [[0 for i in range(n + 1)] for j in range(m + 1)]
		a = self.solve(X, Y, m, n, dp)
		return m + n - a


class Solution:

	def subs(self, X, Y, n, m):
		prev = [0] * (m + 1)
		curr = [0] * (m + 1)
		for i in range(1, n + 1):
			for j in range(1, m + 1):
				if X[i - 1] == Y[j - 1]:
					curr[j] = 1 + prev[j - 1]
				else:
					curr[j] = max(prev[j], curr[j - 1])
			prev = curr[:]
		return prev[-1]

	def shortestCommonSupersequence(self, X, Y, n, m):
		return m + n - self.subs(X, Y, n, m)


class Solution:

	def shortestCommonSupersequence(self, s1, s2, x, y):
		dp = [[0 for j in range(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])
		p = len(s1) - dp[x][y]
		q = len(s2) - dp[x][y]
		return dp[x][y] + p + q


class Solution:

	def shortestCommonSupersequence(self, X, Y, m, n):
		dp = [[-1 for i in range(n + 1)] for j in range(m + 1)]

		def solve1(a, b, s1, s2, dp):
			if a == len(s1) or b == len(s2):
				return 0
			if dp[a][b] != -1:
				return dp[a][b]
			if s1[a] == s2[b]:
				dp[a][b] = 1 + solve1(a + 1, b + 1, s1, s2, dp)
				return dp[a][b]
			else:
				dp[a][b] = max(solve1(a + 1, b, s1, s2, dp), solve1(a, b + 1, s1, s2, dp))
				return dp[a][b]
		return m + n - solve1(0, 0, X, Y, dp)

		def solve(X, Y, m, n, dp):
			if m == 0 or n == 0:
				return m + n
			if dp[m][n] != -1:
				return dp[m][n]
			if X[m - 1] == Y[n - 1]:
				dp[m][n] = 1 + solve(X, Y, m - 1, n - 1, dp)
			else:
				dp[m][n] = 1 + min(solve(X, Y, m - 1, n, dp), solve(X, Y, m, n - 1, dp))
			return dp[m][n]


class Solution:

	def shortestCommonSupersequence(self, X, Y, m, n):
		dp = [[-1 for i in range(n + 1)] for j in range(m + 1)]

		def solve(X, Y, m, n, dp):
			if m == 0 or n == 0:
				return m + n
			if dp[m][n] != -1:
				return dp[m][n]
			if X[m - 1] == Y[n - 1]:
				dp[m][n] = 1 + solve(X, Y, m - 1, n - 1, dp)
			else:
				dp[m][n] = 1 + min(solve(X, Y, m - 1, n, dp), solve(X, Y, m, n - 1, dp))
			return dp[m][n]
		return solve(X, Y, m, n, dp)


class Solution:

	def LCS(self, s1, s2, m, n):
		dp = [[None] * (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:
					dp[i][j] = 0
				elif s1[i - 1] == s2[j - 1]:
					dp[i][j] = 1 + dp[i - 1][j - 1]
				else:
					dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
		return dp[m][n]

	def shortestCommonSupersequence(self, X, Y, m, n):
		L = self.LCS(X, Y, m, n)
		return L + (m - L) + (n - L)