Welcome Back Reader!
In this article we will discuss about the next problem based on "Dynamic Programming" i.e. "Minimum Cost To Make Two String Identical".
Prerequisite of this problem is Longest Common Sequence.
Before you move any further, it is advised that you give this problem a fair try.Let's jump to the problem.
In this problem you are given an array of two strings S1 and S2 and two numbers x and y. The
cost of deleting a character from S1 is x and cost of deleting a character from S2 is y. You can
delete characters from both the strings.
All you have to do is find the minimum cost required to make the given two strings identical.
Sample Input: sea
Sample Output: 17
To make the string-1 sea and string-2 eat similar we need to delete 's' from 'sea' to get 'ea' and 't' from 'eat' to get 'ea'. The cost to remove s will be 10 and the cost to remove t will be 7 which sum to give the answer as 17.
For more clarity of the question, watch this video
- In this problem we need to find the minimum cost to make the given two strings identical using deletion. The cost of deletion of any character from the string-1 is supposed to be x and the cost of deletion of any character from the string-2 is supposed to be y.
- To make the string identical by deletion in order to get minimum cost, we need to retain the similar characters in both the strings following the same order of occurrence; which is basically the longest common subsequence (lcs).
- And we have already learned to get the length of` lcs. We can use the same process to get the length of the longest common subsequence.
- And after getting this length we can calculate the number of deletions which we need to make from each string by subtracting the length of lcs from the length of string-1 and string-2.
- Suppose the difference of length of string-1 and lcs is l1 and the difference of length of string-2 and lcs is l2.
- Therefore the cost of deletion from sting-1 would be (l1 * x) and from string-1 would be (l2*y).
- And the total cost of deletion would become ((l1*x) + (l2*y)).
For more clarity of this part; watch this video
- To start with, define a 2D array of size ((string1.length() + 1 ) * (string2.length() + 1)). And fill the matrix to get the length of the longest common subsequence.
- After completely filling the dp matrix, the length of lcs will be stored at dp.
- Then we calculate the difference between length of string1 and lcs in a variable l1.
- After that we calculate the difference between length of string2 and lcs in a variable l2.
- Then we return the cost which would be ((l1*x) + (l2*y))
For more clarity of the code, watch this video
Time Complexity: O(n*m)
A nested for loop is used to fill the dp matrix which takes time of O(n*m).
Space Complexity: O(n*m)
One n x m sized 2D array is used which condenses to O(n*m).
We hope that this article was helpful. If somehow you are finding it difficult to understand this problem then we advise you to watch our video lecture of this problem.
Trust me it will just get easier to understand after you have watched the solution video. You can contact us via our website. Doubts, suggestions and feedback are always welcomed.
It is also advised that you follow the sequence of modules and questions which is there on our website . Keep practicing more and more problems daily. Meditate enough on each step of each problem.
All the best for an exciting future!