Minimum Number of Deletions and Insertions

Moderate
0/80
profile
Contributed by
75 upvotes
Asked in companies
PhonePeMicrosoftCoding Ninjas

Problem statement

You are given 2 non-empty strings 's1' and 's2' consisting of lowercase English alphabets only.


In one operation you can do either of the following on 's1':

(1) Remove a character from any position in 's1'.

(2) Add a character to any position in 's1'.


Find the minimum number of operations required to convert string 's1' into 's2'.


Example: 
Input: 's1' = "abcd", 's2' = "anc"

Output: 3

Explanation:
Here, 's1' = "abcd", 's2' = "anc".
In one operation remove 's1[3]', after this operation 's1' becomes "abc".    
In the second operation remove 's1[1]', after this operation 's1' becomes "ac".
In the third operation add 'n' in 's1[1]', after this operation 's1' becomes "anc".

Hence, the minimum operations required will be 3. It can be shown that there's no way to convert s1 into s2 in less than 3 moves.


Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line of the input contains a string 's1'.

The second line of the input contains a string 's2'.


Output Format : 
Return the minimum number of operations required to convert string 's1' into 's2'.


Note : 
You do not need to print anything, it has already been taken care of. Just implement the given function.
Sample Input 1 :
aaa
aa


Expected Answer :
1


Output on console :
1


Explanation For Sample Output 1:
For this test case,
's1' = "aaa", 's2' = "aa"

In one operation remove 's1[2]', after this operation 's1' becomes "aa".

Hence, the output will be 1.


Sample Input 2 :
edl 
xcqja
Expected Answer :
8


Output on console :
8


Expected Time Complexity :
Try to do this in O(n*m), where n is the length of string 's1' and 'm' is the length of string 's2'.


Constraints:
1 <= s1.length, s2.length <= 100

Time limit: 1 sec
Hint

What if you know the longest common subsequence(LCS) of str and ptr.

Approaches (3)
Brute Force (Recursion)

Approach: 

 

The basic idea to solve this problem is that we have to minimize the insertion and deletion operation. For minimizing these operations we want the maximum part of the string unchanged so, we want a longest subsequnce which is common in both of the strings this is known as longest common subsequence(LCS), in the strings “aeaea” and “aaae”, “aae” is the lcs. After we know the lcs we can say that (n-lcs) characters we will remove from str and then m-lcs character we will add so the final answer will be n+m-2*lcs. Now, the only task remain is to find the lcs of the two strings. We will sove it recursively, If we are at ith index in str and at jth index in ptr then we have 2 cases, one is when str[i] is equal to ptr[j], in this case we can say that ith and jth characters are included in the LCS and we can move further. 

 

If str[i] is not equal to ptr[j], in this case we have 2 options whether to take the ith character or jth character in the LCS and take the max of both of the cases.

 

Lets define a function “lcs(i, j, n, m, str, ptr) where ‘i’ is the index we are at in str, ‘j’ is the index we are at in ptr, ‘n’ is the length of the string str, ‘m’ is the length of the string ptr.

This function returns the LCS of string str[i..n-1] and ptr[j..m-1]. 

 

Here is the algorithm:

 

  • lcs function:
    • If ‘i’ is equal to ‘n’ or ‘j’ is equal to ‘m’
      • Return 0
    • Declare an integer variable “ans” and initialize it with 0.
    • If str[i] is equal to ptr[j]
      • Update ans as ans = 1 + lcs(i + 1, j + 1, n, m, str, ptr).
    • Else
      • Update ans as ans = max(lcs(i, j + 1, n, m, str, ptr), lcs(i + 1, j, n, m, str, ptr)).
    • Return ans.


 

  • given function:
    • Declare a variable ‘n’ and initialize it with str.length.
    • Declare a variable ‘m’ and initialize it with ptr.length.
    • Declare a variable “len” denoting the length of the longest common subsequence.
    • len = lcs(0, 0, n, m, str, ptr).
    • ans= n + m - 2 * len.
    • Return ans.
Time Complexity

O( 2^(N + M)  ), where 'N' is the length of string "str" and 'M' is the length of the string "ptr".

 

Each time we have ‘N+M’ options from which we have to select one. So, if you try to make the recursive tree you can see each time there will be an ‘N+M’ recursive call generated.


So time complexity will be O( 2^(N + M)  ).

Space Complexity

O(N+M),  where 'N' is the length of string "str" and 'M' is the length of the string "ptr".

 

The recursive stack for the “lcs” function can contain at most ‘N+M’ calls. Therefore, the overall space complexity will be O(N+M).

Code Solution
(100% EXP penalty)
Minimum Number of Deletions and Insertions
Full screen
Console