Redirecting to
NADOS


  Prev   Next

Minimum Cost To Make Two Strings Identical







Luck is a dividend of sweat. The more you sweat, the luckier you get.
~Ray Kroc

Minimum Cost To Make Two Strings Identical

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.

Important Link : Problem Link, Solution Video

Understanding 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.
For example:
Sample Input: sea
eat
10
7
Sample Output: 17

HOW?

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

Approach :
  • 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

Let's try to code this!
public static int solution(String s1, String s2, int c1, int c2) { int[][] dp = new int[s1.length() + 1][s2.length() + 1]; //1 for(int i = 1; i <= s1.length(); i++) { for(int j = 1; j < =s2.length() ; j++) { if(s1.charAt(i - 1) == s2.charAt(j - 1)) { dp[i][j] = dp[i - 1][j - 1] + 1; }else { dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]); } } } int lcs = dp[s1.length()][s2.length()]; //2 int l1 = s1.length() - lcs; //3 int l2 = s2.length() - lcs; //4 return l1 * c1 + l2 * c2; //5 }
java; true";
  1. 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.
  2. After completely filling the dp matrix, the length of lcs will be stored at dp[][].
  3. Then we calculate the difference between length of string1 and lcs in a variable l1.
  4. After that we calculate the difference between length of string2 and lcs in a variable l2.
  5. Then we return the cost which would be ((l1*x) + (l2*y))

For more clarity of the code, watch this video

Complexities:
Time Complexity

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

Space Complexity: O(n*m)
One n x m sized 2D array is used which condenses to O(n*m).

import java.io.*; import java.util.*; public class Main { public static void main(String[] args) { Scanner scn = new Scanner(System.in); String s1 = scn.next(); String s2 = scn.next(); int x = scn.nextInt(); int y = scn.nextInt(); System.out.println(solution(s1, s2,x, y)); } public static int solution(String s1, String s2, int c1, int c2) { int[][] dp = new int[s1.length() + 1][s2.length() + 1]; for(int i = 1; i < = s1.length(); i++) { for(int j = 1; j <= s2.length() ; j++) { if(s1.charAt(i - 1) == s2.charAt(j - 1)) { dp[i][j] = dp[i - 1][j - 1] + 1; }else { dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]); } } } int lcs = dp[s1.length()][s2.length()]; int l1 = s1.length() - lcs; int l2 = s2.length() - lcs; return l1 * c1 + l2 * c2; } }
java; true";

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!
Happy Coding!

Dynamic Programming
String
Author: Nikita Aggarwal
 
Run
Id Name