DP-Interviews
  • Dynamic Programming
  • Notes
    • Equal Subset Sum Partition
    • Longest Increasing Subsequence
    • Maximum Ribbon Cut
    • Largest Divisible Subset
    • Longest Common Substring
    • Unbounded Knapsack
    • Minimum Coin Change
    • Coin Change
    • Target Sum
    • Minimum Subset Sum Difference
    • Rod Cutting
    • Longest Palindromic Substring
    • Longest Bitonic Sequence
    • Longest Repeating Sequence
    • Longest String Chain
    • Natarajan's Birthday Bombs
    • Subsequence Pattern Matching
    • Russian Doll
    • Buy & Sell Stock
    • Maximum Sum Increasing Subsequence
    • Longest Common Subsequence
    • Shortest Common Supersequence
    • 0/1 Knapsack Problem
    • Best Team With No Conflict
    • Count Subset Sum
    • Edit Distance
    • Box-Stacking
    • Longest Palindromic Subsequence
    • All Possible Cuts In All Possible Intervals For Choosing Last Operation
    • Minimum Deletions & Insertions To Transform a String into another
    • Regular Expression Matching
    • Wildcard Matching
    • Optimal Paths To Target
Powered by GitBook
On this page

Was this helpful?

  1. Notes

Minimum Deletions & Insertions To Transform a String into another

PreviousAll Possible Cuts In All Possible Intervals For Choosing Last OperationNextRegular Expression Matching

Last updated 3 years ago

Was this helpful?

Given strings s1 and s2, we need to transform s1 into s2 by deleting and inserting characters. Write a function to calculate the count of the minimum number of deletion and insertion operations.

Example 1:

Input: s1 = "abc"
       s2 = "fbc"
Output: 1 deletion and 1 insertion.
Explanation: We need to delete {'a'} and insert {'f'} to s1 to transform it into s2.

Example 2:

Input: s1 = "abdca"
       s2 = "cbda"
Output: 2 deletions and 1 insertion.
Explanation: We need to delete {'a', 'c'} and insert {'c'} to s1 to transform it into s2.

Solution

This problem can easily be converted to the Longest Common Subsequence (LCS). If we can find the LCS of the two input strings, we can easily find how many characters we need to insert and delete from s1. Here is how we can do this:

  1. Let’s assume len1 is the length of s1 and len2 is the length of s2.

  2. Now let’s assume c1 is the length of LCS of the two strings s1 and s2.

  3. To transform s1 into s2, we need to delete everything from s1 which is not part of LCS, so minimum deletions we need to perform from s1 => len1 - c1

  4. Similarly, we need to insert everything in s1 which is present in s2 but not part of LCS, so minimum insertions we need to perform in s1 => len2 - c1

The time and space complexity for this is O(m*n), where ‘m’ and ‘n’ are the lengths of the two input strings.

Code