Given two strings str1 and str2. The task is to remove or insert the minimum number of characters from/in str1 so as to transform it into str2. It could be possible that the same character needs to be removed/deleted from one point of str1 and inserted to some another point.
Example 1:
Input: str1 = "heap", str2 = "pea"
Output: 3
Explanation: 2 deletions and 1 insertion
p and h deleted from heap. Then, p is 
inserted at the beginning One thing to 
note, though p was required yet it was 
removed/deleted first from its position 
and then it is inserted to some other 
position. Thus, p contributes one to the 
deletion_count and one to the 
insertion_count.
Example 2:
Input : str1 = "geeksforgeeks"
str2 = "geeks"
Output: 8
Explanation: 8 deletions
 
Your Task:
You don't need to read or print anything. Your task is to complete the function minOperations() which takes both strings as input parameter and returns the minimum number of operation required.
Expected Time Complexity: O(|str1|*|str2|)
Expected Space Complexity: O(|str1|*|str2|)
Constraints:
1 ≤ |str1|, |str2| ≤ 1000
All the characters are lower case English alphabets

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Dynamic programming

Starter code: #User function Template for python3
class Solution:
	def minOperations(self, s1, s2):
		# code here

Solutions:
class Solution:

	def minOperations(self, s1, s2):
		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])
		lcs = dp[n][m]
		return n - lcs + (m - lcs)


class Solution:

	def minOperations(self, s, t):
		n = len(s)
		m = len(t)
		dp = [[0 for i in range(m + 1)] for j in range(n + 1)]
		ans = 1000000000.0
		for i in range(1, n + 1):
			for j in range(1, m + 1):
				if s[i - 1] == t[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 m - dp[n][m] + (n - dp[n][m])


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 minOperations(self, s1, s2):
		return len(s1) - self.lcs(s1, s2) + len(s2) - self.lcs(s1, s2)


class Solution:

	def minOperations(self, s1, s2):
		lcs = tabulation(s1, s2, len(s1), len(s2))
		return len(s1) + len(s2) - 2 * lcs

def tabulation(s1, s2, n, m) -> int:
	t = [[0] * (m + 1) for i in range(n + 1)]
	ans = 0
	for i in range(1, n + 1):
		for j in range(1, m + 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[n][m]


class Solution:

	def minOperations(self, s1, s2):
		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 - 2 * 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 minOperations(self, s1, s2):
		a = len(s1)
		b = len(s2)
		lcs_ = self.lcs(s1, s2, a, b)
		return a + b - 2 * lcs_


class Solution:

	def minOperations(self, s1, s2):
		n = len(s1)
		m = len(s2)
		prev = [0 for i in range(m + 1)]
		for i in range(1, n + 1):
			temp = [0 for i in range(m + 1)]
			for j in range(1, m + 1):
				if s1[i - 1] == s2[j - 1]:
					temp[j] = 1 + prev[j - 1]
				else:
					temp[j] = max(prev[j], temp[j - 1])
			prev = temp
			prev[0] = 0
		return n + m - prev[m] * 2


class Solution:

	def helper(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]:
			return 1 + self.helper(i - 1, j - 1, s1, s2, dp)
		else:
			dp[i][j] = max(self.helper(i - 1, j, s1, s2, dp), self.helper(i, j - 1, s1, s2, dp))
			return dp[i][j]

	def minOperations(self, s1, s2):
		m = len(s1)
		n = len(s2)
		dp = [[-1] * (n + 1) for i in range(m + 1)]
		lenOfComSubsequence = self.helper(m - 1, n - 1, s1, s2, dp)
		return m + n - 2 * lenOfComSubsequence


class Solution:

	def minOperations(self, s1, s2):
		dp = [[0 for j in range(len(s2) + 1)] for i 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]:
					answer = 1 + dp[i - 1][j - 1]
				else:
					answer = max(dp[i][j - 1], dp[i - 1][j])
				dp[i][j] = answer
		modification = len(s1) + len(s2) - 2 * dp[-1][-1]
		return modification


def maxLength(dp):
	ans = 0
	for i in range(len(dp)):
		for j in range(len(dp[0])):
			ans = max(ans, dp[i][j])
	return ans

def helper(s1, s2, dp, x, y):
	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 + helper(s1, s2, dp, x - 1, y - 1)
		return dp[x][y]
	else:
		dp[x][y] = max(helper(s1, s2, dp, x - 1, y), helper(s1, s2, dp, x, y - 1))
		return dp[x][y]

class Solution:

	def minOperations(self, s1, s2):
		(x, y) = (len(s1), len(s2))
		dp = [[-1 for _ in range(len(s2) + 1)] for _ in range(len(s1) + 1)]
		helper(s1, s2, dp, x, y)
		temp = maxLength(dp)
		del_cnt = x - temp
		ins_cnt = y - temp
		return del_cnt + ins_cnt


class Solution:

	def minOperations(self, s1, s2):
		n = len(s1)
		m = len(s2)
		x = self.lcs(n, m, s1, s2)
		ans = n - x + m - x
		return ans

	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 minOperations(self, s1, s2):
		m = len(s1)
		n = len(s2)
		dp = [[-1 for _ in range(n + 1)] for _ in range(m + 1)]
		lcs = self.ls(m, n, s1, s2, dp)
		noofdeletions = len(s1) - lcs
		noofinsertions = len(s2) - lcs
		return noofdeletions + noofinsertions


class Solution:

	def minOperations(self, string1, string2):
		cache = {}

		def LCS(indx1, indx2):
			if indx1 >= len(string1) or indx2 >= len(string2):
				return abs(len(string1) - indx1) + abs(len(string2) - indx2)
			if (indx1, indx2) in cache:
				return cache[indx1, indx2]
			if string1[indx1] == string2[indx2]:
				cache[indx1, indx2] = LCS(indx1 + 1, indx2 + 1)
			else:
				cache[indx1, indx2] = min(1 + LCS(indx1 + 1, indx2), 1 + LCS(indx1, indx2 + 1))
			return cache[indx1, indx2]
		return LCS(0, 0)


class Solution:

	def minOperations(self, s1, s2):
		a = len(s1)
		b = len(s2)
		dp = [[0] * (b + 1) for i in range(a + 1)]
		for i in range(1, b + 1):
			dp[0][i] = i
		for i in range(1, a + 1):
			dp[i][0] = i
		for i in range(1, a + 1):
			charA = s1[i - 1]
			for j in range(1, b + 1):
				charB = s2[j - 1]
				if charB == charA:
					dp[i][j] = dp[i - 1][j - 1]
				else:
					dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1])
		return dp[a][b]


class Solution:

	def minOperations(self, s1, s2):
		dp = dict()

		def go(i, j):
			if i < 0 and j < 0:
				return 0
			if i < 0:
				return j + 1
			if j < 0:
				return i + 1
			if (i, j) in dp:
				return dp[i, j]
			if s1[i] == s2[j]:
				ans = go(i - 1, j - 1)
			else:
				ans = 1 + min(go(i - 1, j), go(i, j - 1))
			dp[i, j] = ans
			return ans
		a = len(s1)
		b = len(s2)
		return go(a - 1, b - 1)


class Solution:

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

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


class Solution:

	def recur(self, i1, i2, s1, s2, dp):
		if i1 < 0 or i2 < 0:
			return 0
		if dp[i1][i2] != -1:
			return dp[i1][i2]
		if s1[i1] == s2[i2]:
			dp[i1][i2] = 1 + self.recur(i1 - 1, i2 - 1, s1, s2, dp)
			return dp[i1][i2]
		else:
			dp[i1][i2] = max(self.recur(i1 - 1, i2, s1, s2, dp), self.recur(i1, i2 - 1, s1, s2, dp))
			return dp[i1][i2]

	def minOperations(self, s1, s2):
		n = len(s1)
		m = len(s2)
		dp = [[-1 for _ in range(m)] for _ in range(n)]
		lcs = self.recur(n - 1, m - 1, s1, s2, dp)
		return m - lcs + (n - lcs)


class Solution:

	def minOperations(self, s1, s2):
		m = len(s1)
		n = len(s2)
		X = s1
		Y = s2
		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 - 2 * ans


class Solution:
	dp = []

	def gen(self, s1, s2, r1, r2):
		if r1 < 0 or r2 < 0:
			return abs(r1 - r2)
		l = 99999
		if self.dp[r1][r2] != -1:
			return self.dp[r1][r2]
		if s1[r1] == s2[r2]:
			l = self.gen(s1, s2, r1 - 1, r2 - 1)
		m = self.gen(s1, s2, r1 - 1, r2) + 1
		n = self.gen(s1, s2, r1, r2 - 1) + 1
		self.dp[r1][r2] = min(l, m, n)
		return min(l, m, n)

	def minOperations(self, s1, s2):
		self.dp = []
		for i in range(len(s1) + 1):
			b = []
			for j in range(len(s2)):
				b.append(-1)
			self.dp.append(b)
		a = self.gen(s1, s2, len(s1) - 1, len(s2) - 1)
		return a


class Solution:

	def minOperations(self, s1, s2):
		st1 = s1
		st2 = s2
		m = len(st1)
		n = len(st2)
		dp = [[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 st1[i - 1] == st2[j - 1]:
					dp[i][j] = 1 + dp[i - 1][j - 1]
				else:
					dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
		length = dp[m][n]
		deletion = m - length
		insertion = n - length
		return insertion + deletion


class Solution:

	def minOperations(self, s1, s2):
		m = len(s1)
		n = len(s2)
		dp = [[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 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])
		ins = m - dp[m][n]
		dele = n - dp[m][n]
		res = ins + dele
		return res


class Solution:

	def minOperations(self, s1, s2):
		m = len(s1)
		n = len(s2)
		dp = [[0] * (n + 1) for _ in range(m + 1)]
		for i in range(m + 1):
			for j in range(n + 1):
				x = i
				y = j
				if x == 0 or y == 0:
					dp[i][j] = 0
				elif s1[x - 1] == s2[y - 1]:
					dp[i][j] = 1 + dp[x - 1][y - 1]
				else:
					dp[i][j] = max(dp[x - 1][y], dp[x][y - 1])
		ans = dp[m][n]
		de = abs(m - ans)
		ins = abs(ans - n)
		return de + ins


class Solution:

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


class Solution:

	def minOperations(self, s1, s2):
		dp = [[0 for i in range(len(s2) + 1)] for _ in range(len(s1) + 1)]
		for i in range(len(s1) + 1):
			for j in range(len(s2) + 1):
				if i == len(s1) and j != len(s2):
					dp[i][j] = len(s2) - j
				elif i != len(s1) and j == len(s2):
					dp[i][j] = len(s1) - i
		for i in range(len(s1) - 1, -1, -1):
			for j in range(len(s2) - 1, -1, -1):
				if s1[i] == s2[j]:
					dp[i][j] = dp[i + 1][j + 1]
				else:
					inse = 1 + dp[i][j + 1]
					delet = 1 + dp[i + 1][j]
					dp[i][j] = min(inse, delet)
		return dp[0][0]


class Solution:

	def minOperations(self, s1, s2):

		def find(s1, s2, i, j, dp):
			if i == len(s1) and j == len(s2):
				return 0
			if i == len(s1) and j != len(s2):
				return len(s2) - j
			if i != len(s1) and j == len(s2):
				return len(s1) - i
			if dp[i][j] != -1:
				return dp[i][j]
			skip = 9999999
			inse = 9999999
			delet = 999999
			if s1[i] == s2[j]:
				skip = find(s1, s2, i + 1, j + 1, dp)
			else:
				inse = 1 + find(s1, s2, i, j + 1, dp)
				delet = 1 + find(s1, s2, i + 1, j, dp)
			dp[i][j] = min(skip, inse, delet)
			return dp[i][j]
		dp = [[-1 for i in range(len(s2) + 1)] for _ in range(len(s1) + 1)]
		return find(s1, s2, 0, 0, dp)


class Solution:

	def lcs(self, s1, s2):
		n = len(s1)
		m = len(s2)
		prev = [0] * (m + 1)
		cur = [0] * (m + 1)
		for ind1 in range(1, n + 1):
			for ind2 in range(1, m + 1):
				if s1[ind1 - 1] == s2[ind2 - 1]:
					cur[ind2] = 1 + prev[ind2 - 1]
				else:
					cur[ind2] = 0 + max(prev[ind2], cur[ind2 - 1])
			prev = cur[:]
		return prev[m]

	def minOperations(self, s1, s2):
		(n, m) = (len(s1), len(s2))
		k = self.lcs(s1, s2)
		return n - k + (m - k)


class Solution:

	def minOperations(self, s1, s2):

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


import itertools

class Solution:

	def minOperations(self, s1, s2):
		m = len(s1)
		n = len(s2)
		dp = [[0] * (n + 1) for _ in range(m + 1)]
		for (i, j) in itertools.product(range(1, m + 1), range(1, n + 1)):
			dp[i][j] = 1 + dp[i - 1][j - 1] if s1[i - 1] == s2[j - 1] else max(dp[i - 1][j], dp[i][j - 1])
		ins = m - dp[m][n]
		dele = n - dp[m][n]
		return ins + dele


class Solution:

	def minOperations(self, s1, s2):
		dp = [[float('inf')] * (len(s2) + 1) for i in range(len(s1) + 1)]
		for i in range(len(s1)):
			dp[i][-1] = i + 1
		for j in range(len(s2)):
			dp[-1][j] = j + 1
		dp[-1][-1] = 0
		for i in range(len(s1)):
			for j in range(len(s2)):
				dp[i][j] = dp[i - 1][j - 1] if s1[i] == s2[j] else min(dp[i - 1][j], dp[i][j - 1]) + 1
		return dp[len(s1) - 1][len(s2) - 1]


class Solution:

	def minOperations(self, s1, s2):
		delete = 0
		insert = 0
		n = len(s1)
		m = len(s2)
		res = self.f(s1, s2, n, m)
		delete = n - res
		insert = m - res
		return delete + insert

	def f(self, s1, s2, n, m):
		dp = [[0 for i in range(m + 1)] for j in range(n + 1)]
		ans = 0
		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 f(self, s1, s2, ind1, ind2, dp):
		if ind1 < 0 or ind2 < 0:
			return 0
		if dp[ind1][ind2] != -1:
			return dp[ind1][ind2]
		if s1[ind1] == s2[ind2]:
			dp[ind1][ind2] = 1 + self.f(s1, s2, ind1 - 1, ind2 - 1, dp)
			return dp[ind1][ind2]
		dp[ind1][ind2] = 0 + max(self.f(s1, s2, ind1, ind2 - 1, dp), self.f(s1, s2, ind1 - 1, ind2, dp))
		return dp[ind1][ind2]

	def minOperations(self, s1, s2):
		dp = [[-1 for i in range(len(s2))] for j in range(len(s1))]
		a = self.f(s1, s2, len(s1) - 1, len(s2) - 1, dp)
		deletion = len(s1) - a
		insertion = len(s2) - a
		return deletion + insertion


class Solution:

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


class Solution:

	def minOperations(self, s1, s2):

		def lcs(x, y, s1, s2):
			T = [[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]:
						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]
		return len(s1) + len(s2) - 2 * lcs(len(s1), len(s2), s1, s2)


class Solution:

	def lcs(self, str1, str2):
		m = len(str1)
		n = len(str2)
		dp = [[-1] * (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
		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 minOperations(self, s1, s2):
		lcs = self.lcs(s1, s2)
		deletions = len(s1) - lcs
		insertions = len(s2) - lcs
		return deletions + insertions


class Solution:

	def minOperations(self, s1, s2):
		(m, n) = (len(s1), len(s2))
		from functools import lru_cache

		@lru_cache(None)
		def solve(m, n):
			if m == 0:
				return [0, n]
			if n == 0:
				return [m, 0]
			if s1[m - 1] == s2[n - 1]:
				return solve(m - 1, n - 1)
			a1 = solve(m - 1, n)
			a2 = solve(m, n - 1)
			if sum(a1) < sum(a2):
				return [a1[0] + 1, a1[1]]
			return [a2[0], a2[1] + 1]
		return sum(solve(m, n))


class Solution:

	def minOperations(self, s1, s2):
		(m, n) = (len(s1), len(s2))
		import functools

		@functools.lru_cache(None)
		def solve(m, n):
			if m == 0:
				return n
			if n == 0:
				return m
			if s1[m - 1] == s2[n - 1]:
				return solve(m - 1, n - 1)
			return min(solve(m, n - 1), solve(m - 1, n)) + 1
		return solve(m, n)


class Solution:

	def minOperations(self, s1, s2):
		n = len(s1)
		m = len(s2)
		c = self.fun(m, n)
		return n - c + m - c

	def fun(self, n, m):
		dp = [[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:
					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[m][n]


class Solution:

	def minOperations(self, s1, s2):
		dp = [[-1 for j in range(len(s2) + 1)] for i in range(len(s1) + 1)]
		for i in range(len(s1) + 1):
			dp[i][0] = 0
		for i in range(len(s2) + 1):
			dp[0][i] = 0
		for ind1 in range(1, len(s1) + 1):
			for ind2 in range(1, len(s2) + 1):
				match = notmatch = 0
				if s1[ind1 - 1] == s2[ind2 - 1]:
					match = 1 + dp[ind1 - 1][ind2 - 1]
				else:
					notmatch = max(dp[ind1 - 1][ind2], dp[ind1][ind2 - 1])
				dp[ind1][ind2] = max(match, notmatch)
		return len(s1) + len(s2) - 2 * dp[len(s1)][len(s2)]


class Solution:

	def minOperations(self, s1, s2):
		dp = [[-1 for a in range(len(s2))] for b in range(len(s1))]

		def solve(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 + solve(i - 1, j - 1)
			else:
				dp[i][j] = max(solve(i - 1, j), solve(i, j - 1))
			return dp[i][j]
		a = solve(len(s1) - 1, len(s2) - 1)
		lS1 = len(s1) - a
		lS2 = len(s2) - a
		return lS1 + lS2


class Solution:

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


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 minOperations(self, s1, s2):
		m = len(s1)
		n = len(s2)
		i = m - self.LCS(s1, s2, m, n)
		d = n - self.LCS(s1, s2, m, n)
		return i + d


class Solution:

	def minOperations(self, s1, s2):

		def computeLCS(str1, str2):
			(m, n) = (len(str1), len(str2))
			dp = [[-1 for j in range(n + 1)] for i in range(m + 1)]
			for j in range(n + 1):
				dp[0][j] = 0
			for i in range(1, m + 1):
				dp[i][0] = 0
			for i in range(1, m + 1):
				for j in range(1, n + 1):
					(ch1, ch2) = (str1[i - 1], str2[j - 1])
					if ch1 == ch2:
						dp[i][j] = 1 + dp[i - 1][j - 1]
					else:
						dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])
			return dp[m][n]
		(l1, l2) = (len(s1), len(s2))
		lcs = computeLCS(s1, s2)
		ans = l1 - lcs + (l2 - lcs)
		return ans


class Solution:

	def minOperations(self, s1, s2):
		m = len(s1)
		n = len(s2)
		prev = [0 for j in range(n + 1)]
		curr = [0 for j in range(n + 1)]
		for index1 in range(1, m + 1):
			for index2 in range(1, n + 1):
				if s1[index1 - 1] == s2[index2 - 1]:
					curr[index2] = prev[index2 - 1] + 1
				else:
					curr[index2] = max(curr[index2 - 1], prev[index2])
			prev = curr[:]
		res = curr[n]
		s1_remaining = abs(m - res)
		s2_remaining = abs(n - res)
		return s1_remaining + s2_remaining


class Solution:

	def minOperations(self, str1, str2):
		(m, n) = (len(str1), len(str2))
		dp = [[0 for x in range(n + 1)] for x in range(m + 1)]
		for i in range(m + 1):
			for j in range(n + 1):
				if i == 0:
					dp[i][j] = j
				elif j == 0:
					dp[i][j] = i
				elif str1[i - 1] == str2[j - 1]:
					dp[i][j] = dp[i - 1][j - 1]
				else:
					dp[i][j] = 1 + min(dp[i][j - 1], dp[i - 1][j])
		return dp[m][n]


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 minOperations(self, s1, s2):
		m = len(s1)
		n = len(s2)
		dp = [[-1 for i in range(n + 1)] for j in range(m + 1)]
		count = self.find_lcs(dp, s1, s2, m, n)
		return m + n - 2 * count


class Solution:

	def f(self, s, t, x, y):
		prev = [0] * (y + 1)
		for ind1 in range(1, x + 1):
			curr = [0] * (y + 1)
			for ind2 in range(1, y + 1):
				if s[ind1 - 1] == t[ind2 - 1]:
					curr[ind2] = 1 + prev[ind2 - 1]
				else:
					curr[ind2] = max(prev[ind2], curr[ind2 - 1])
			prev = curr
		return prev[y]

	def minOperations(self, s1, s2):
		n = len(s1)
		m = len(s2)
		lcs = self.f(s1, s2, n, m)
		deletions = n - lcs
		insetions = m - lcs
		return deletions + insetions


class Solution:

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

	def minOperations(self, s1, s2):
		n = len(s1)
		m = len(s2)
		sub = self.subs(s1, s2)
		dele = n - sub
		ins = m - sub
		return dele + ins


class Solution:

	def minOperations(self, s1, s2):
		t1 = s1
		t2 = s2
		n1 = len(t1)
		n2 = len(t2)
		dp = [[0 for j in range(n2 + 1)] for i in range(n1 + 1)]
		for i in range(1, n1 + 1):
			for j in range(1, n2 + 1):
				if t1[i - 1] == t2[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 n1 + n2 - 2 * dp[n1][n2]


class Solution:

	def minOperations(self, s1, s2):
		text1 = s1
		text2 = s2
		n = len(text1)
		m = len(text2)
		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 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 n + m - 2 * dp[n][m]


class Solution:

	def SpaceOptimized(self, ind1, ind2, str1, str2):
		prev = [0] * (ind2 + 1)
		dp = [0] * (ind2 + 1)
		for row in range(1, ind1 + 1):
			for col in range(1, ind2 + 1):
				if str1[row - 1] == str2[col - 1]:
					dp[col] = 1 + prev[col - 1]
				else:
					val1 = val2 = 0
					val1 = prev[col]
					val2 = dp[col - 1]
					dp[col] = max(val1, val2)
			prev = list(dp)
		return prev[ind2]

	def minOperations(self, s1, s2):
		k = self.SpaceOptimized(len(s1), len(s2), s1, s2)
		deletions = len(s1) - k
		insertions = len(s2) - k
		return deletions + insertions


class Solution:

	def minOperations(self, s1, s2):
		n = len(s1)
		m = len(s2)
		prev = [0 for _ in range(m + 1)]
		curr = [0 for _ in range(m + 1)]
		for row in range(1, n + 1):
			for col in range(1, m + 1):
				if s1[row - 1] == s2[col - 1]:
					curr[col] = 1 + prev[col - 1]
				else:
					curr[col] = max(prev[col], curr[col - 1])
			prev = list(curr)
		return n + m - 2 * prev[m]


class Solution:

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

		def solve(m, n):
			if m == l1 or n == l2:
				return 0
			elif dp[m][n] != -1:
				return dp[m][n]
			elif s1[m] == s2[n]:
				dp[m][n] = 1 + solve(m + 1, n + 1)
			else:
				dp[m][n] = max(solve(m + 1, n), solve(m, n + 1))
			return dp[m][n]
		a = solve(0, 0)
		return l1 - a + (l2 - a)


class Solution:

	def minOperations(self, s1, s2):
		m = len(s1)
		n = len(s2)
		memo = [[-1 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:
					memo[i][j] = 0
				elif s1[i - 1] == s2[j - 1]:
					memo[i][j] = 1 + memo[i - 1][j - 1]
				else:
					memo[i][j] = max(memo[i][j - 1], memo[i - 1][j])
		ans = m - memo[-1][-1] + (n - memo[-1][-1])
		return ans


class Solution:

	def minOperations(self, s1, s2):
		n = len(s1)
		m = len(s2)
		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 s1[i - 1] == s2[j - 1]:
					res[i][j] = 1 + res[i - 1][j - 1]
				else:
					res[i][j] = max(res[i - 1][j], res[i][j - 1])
		return n - res[n][m] + (m - res[n][m])


class Solution:

	def minOperations(self, s1, s2):
		lcs = LCSDP(s1, s2, len(s1), len(s2))
		numOfDel = len(s1) - lcs
		numOfIns = len(s2) - lcs
		return numOfDel + numOfIns

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


class Solution:

	def minOperations(self, s1, s2):
		l1 = len(s1)
		l2 = len(s2)
		dp = [[0 for x in range(l2 + 1)] for x in range(l1 + 1)]
		for i in range(l1 + 1):
			for j in range(l2 + 1):
				if i * j == 0:
					dp[i][j] = 0
		for i in range(1, l1 + 1):
			for j in range(1, l2 + 1):
				ind1 = i - 1
				ind2 = j - 1
				if s1[ind1] == s2[ind2]:
					dp[i][j] = dp[i - 1][j - 1] + 1
				else:
					dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
		dele = max(l1, l2) - dp[l1][l2]
		ins = min(l1, l2) - dp[l1][l2]
		return ins + dele


class Solution:

	def minOperations(self, s1, s2):
		n1 = len(s1)
		n2 = len(s2)
		dp = [[0 for _ in range(n1 + 1)] for _ in range(n2 + 1)]
		for i in range(1, n2 + 1):
			for j in range(1, n1 + 1):
				if s1[j - 1] == s2[i - 1]:
					dp[i][j] = 1 + dp[i - 1][j - 1]
				else:
					dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
		deletions = n1 - dp[n2][n1]
		insertions = n2 - dp[n2][n1]
		return insertions + deletions