Home »
Interview coding problems/challenges
Minimum Cost to Make Two Strings Identical
Minimum Cost to Make Two Strings Identical: Here, we are going to see a standard dynamic programming (DP) problem on edit distance which can be featured in any interview rounds.
Submitted by Radib Kar, on April 22, 2020
Problem statement:
Given two strings string1 and string2 find the minimum cost required to make the given two strings identical. We can delete characters from both the strings. The cost of deleting a character from string1 is costX and string2 is costY. The cost of removing any characters from the same string is the same. Like, removing any
Input:
The first line contains integers costX and costY.
The second line contains the two strings X and Y.
Output:
Print the total cost to make the two strings
equal for each test case in a new line.
Constraints:
1<= length of strings X and Y <=1000
1<= costX, costY <=1000
Explanation of Example:
Input:
1
10 20
"acba" "acdb"
Output:
30
Explanation:
The similar strings would be "acb".
So need to remove one from string1 and one from string2
costing total of 30.
Solution Approach:
The problem can be solved recursively,
Let,
N = length of string1
M = length of string1
F(n,m) = minimum cost to make two strings similar
Let us consider, what can be cases that can arrive for F(i,j) where 0 <= i<n && 0 <= j<m
Case 1.
string1[i]==string2[j] that is indexed characters are similar
In such a case, we don't need any additional cost to make strings similar, the cost will be similar to subproblem of size i1, j1. This can be recursively written as
F(i,j) = F(i1,j1) if string1[i] == string2[j]
Case 2.
string1[i]!=string2[j] that is indexed characters are not similar.
In such a case we need to invest,

One thing can remove the indexed character from string1 and change to indexed string2 character.
This can be recursively written as,
F(i,j) = F(i1,j) + costX if string1[i] != string2[j]

Another way can be to remove the indexed character from string2 and change to string1 indexed character.
This can be recursively written as,
F(i,j) = F(i,j1) + costY if string1[i] != string2[j]

Remove characters from both.
This can be recursively written as,
F(i,j) = F(i1,j1) + costY + costX if string1[i] != string2[j]
Finally, we would take minimum out of this three cases.
So here goes the problem structure,
Now the above recursion will create many overlapping subproblems and hence we need two converts it into DP.
Converting into DP
n = string1 length
m = string2 length
str1 = string1
str2 = string2
1) Declare int dp[n+1][m+1];
2) Base case
for i=0 to n
dp[i][0]=i*costX;
for j=0 to m
dp[0][j]=j*costY;
3) Fill the DP
for i=1 to n
for j=1 to m
//first case when str1[i1]==str2[j1]
dp[i][j]=dp[i1][j1];
if(str1[i1]!=str2[j1])
dp[i][j]+=costX+costY;
dp[i][j]=min(dp[i][j],min(dp[i1][j]+costX,dp[i][j1]+costY));
end if
end for
end for
4) return dp[n][m];
C++ Implementation:
#include <bits/stdc++.h>
using namespace std;
int editdistance(string s1, string s2, int costX, int costY)
{
int n = s1.length();
int m = s2.length();
int dp[n + 1][m + 1];
for (int i = 0; i <= n; i++)
dp[i][0] = i * costX;
for (int j = 0; j <= m; j++)
dp[0][j] = j * costY;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
dp[i][j] = dp[i  1][j  1];
if (s1[i  1] != s2[j  1]) {
dp[i][j] += costX + costY;
dp[i][j] = min(dp[i][j], min(dp[i  1][j] + costX, dp[i][j  1] + costY));
}
}
}
return dp[n][m];
}
int main()
{
int costX, costY;
cout << "Cost of changing/removing character from string1: \n";
cin >> costX;
cout << "Cost of changing/removing character from string2: \n";
cin >> costY;
string s1, s2;
cout << "Input string1\n";
cin >> s1;
cout << "Input string2\n";
cin >> s2;
cout << "Minimum cost to make two string similar: " << editdistance(s1, s2, costX, costY) << endl;
return 0;
}
Output
Cost of changing/removing character from string1:
2
Cost of changing/removing character from string2:
3
Input string1
includehelp
Input string2
includuggu
Minimum cost to make two string similar: 22
TOP Interview Coding Problems/Challenges