Given two strings ‘str1’ and ‘str2’ of size m and n respectively. The task is to remove/delete and insert the minimum number of characters from/in str1 to transform it into str2. It could be possible that the same character needs to be removed/deleted from one point of str1 and inserted to some another point.
Note: Here operation (insertion/deletion) has to be performed only on string str1 only.
Example 1:
Input :
str1 = "heap", str2 = "pea"
Output :
Minimum Deletion = 2 and
Minimum Insertion = 1
Explanation:p andh deleted fromheap
Then,p is inserted at the beginning
One thing to note, thoughp was required yet
it was removed/deleted first from its position and
then it is inserted to some other position.
Thus,p contributes one to thedeletion_count
and one to theinsertion_count.
Minimum number of deletions and insertions to transform one string into another - GeeksforGeeks
str1 and str2 be the given strings.
m and n be their lengths respectively.
len be the length of the longest common subsequence of str1 and str2
minimum number of deletions minDel = m – len
minimum number of Insertions minInsert = n – len
Time and Space Complexity of the above implementation is O(mn)