Minimum Number of Deletions and Insertions

Statement

Given two strings, str1 and str2, find the minimum number of deletions and insertions required to transform str1 into str2.

Note: This problem has a direct application in the autocorrect feature. It is also used in bioinformatics to quantify the similarity between two DNA sequences.

For example, if we want to transform str1 “pqr” into str2 “tqr”, we need to delete “p” and insert “t” in str1. Therefore, the minimum number of deletions and insertions required are:

• Deletions: $1$
• Insertions: $1$

Constraints:

• $1 \leq$ str1.length, str2.length $\leq 500$
• str1 and str2 are in the same case English letters.

Examples

Try it yourself

Implement your solution in the following playground.

Note: If you clicked the “Submit” button and the code timed out, this means that your solution needs to be optimized.

Hint: Use dynamic programming and see the magic.

Solution

We will first explore the naive recursive solution to this problem and then see how it can be improved using the Longest Common Substring dynamic programming pattern.

Naive approach

A naive approach is to process all the characters of each string, one by one. Starting from the first character of both strings, there are three possibilities for every pair of characters being considered:

• The first characters of both the strings match, in which case, we increment the count of the matching characters by 1. We move one position ahead in both strings, and the function is called recursively on the remaining strings.

• The first characters of both the strings do not match, in which case, the following possibilities are checked on both strings:

  • A recursive call by moving one position ahead in the