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

Constraints:

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

Examples

Level up your interview prep. Join Educative to access 80+ hands-on prep courses.