# Delete Operation for Two Strings (Leetcode 583)

## Problem Description

Given two strings word1 and word2, return the minimum number of steps required to make word1 and word2 the same.

In one step, you can delete exactly one character in either string.

### Examples

Input: word1 = "sea", word2 = "eat"
Output: 2
Explanation: You need one step to make "sea" to "ea" and another step to make "eat" to "ea".
Input: word1 = "leetcode", word2 = "etco"
Output: 4

### Constraints

• 1 <= word1.length, word2.length <= 500
• word1 and word2 consist of only lowercase English letters.

## Solution

The problem might sound familiar to classic dynamic programming questions however we should focus that we can only delete the words. If we were allowed to update / insert / delete the characters then it would have become the Edit Distance Problem using Dynamic Programming. Because we are only allowed using the delete operation, the problem translates to finding the number of characters that are different in both the strings (or finding the common ones?). If We can easily find the common subsequence characters and subtract double the common length from the combined length, it would give us the letters we want to delete. We can use the Longest Common Subsequence for that and we will briefly discuss about the algorithm and I would put more references in case you want to learn more about the algorithm.

### Longest Common subsequence

To determine the length of the LCS between all combinations of substrings of a and b, we can use a dynamic programming technique. Dynamic programming basically means that you compute all possibilities and store them inside a look-up table.

To find the lengths of all possible subsequences, we use a helper function, lcsLength(_:). This creates a matrix of size (n+1) by (m+1), where matrix[x][y] is the length of the LCS between the substrings a[0...x-1] and b[0...y-1].

Lets take an example for "ABCBX" and "ABDCAB". The following would look something like this:

|   | Ø | A | B | D | C | A | B |
| Ø | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| A | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
| B | 0 | 1 | 2 | 2 | 2 | 2 | 2 |
| C | 0 | 1 | 2 | 2 | 3 | 3 | 3 |
| B | 0 | 1 | 2 | 2 | 3 | 3 | 4 |
| X | 0 | 1 | 2 | 2 | 3 | 3 | 4 |

Note that the elements first row and the first column are 0 since we are comparing with the empty string. In this example, if we look at matrix[3][4] we find the value 3. This means the length of the LCS between a[0...2] and b[0...3], or between "ABC" and "ABDC", is 3.

## Complexity Analysis

The time and space complexity would remain same as the LCS operation. We are using two nested loops to compute the DP array hence m * n operations where m, n are the length of the input strings. Space complexity would also be same for saving 2D matrix.

Time = O(M * N)

Space = O(M * N)