Grokking Dynamic Programming Interview/

...

/

Minimum Number of Deletions and Insertions

Minimum Number of Deletions and Insertions

Let's solve the Minimum Number of Deletions and Insertions problem using Dynamic Programming.

We'll cover the following...

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: 11
  • Insertions: 11

Constraints:

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

Examples

No.

str1

str2

Deletions

Insertions

1

heap

pea

2

1

2

passport

ppsspt

3

1

3

bed

read

1

2

Try it yourself

Implement your solution in the following playground.

Press + to interact
usercode > MinNumDelIns.java
import java.util.*;
public class MinNumDelIns{
    public static int[] minDelIns (String str1, String str2) {
        // your code will replace the placeholder return statement below
        return new int[]{0, 0};
    }
}
Minimum Number of Deletions and Insertions

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
...
Access this course and 1400+ top-rated courses and projects.