Minimum cost to make two strings same
Given four integers a, b, c, d and two strings S1 and S2 of equal length, which consist only of the characters ‘2’, ‘1’ and ‘0’.
- Converting ‘1’ to ‘2’ or vice versa costs a.
- Converting ‘2’ to ‘3’ or vice versa costs b.
- Converting ‘3’ to ‘1’ or vice versa costs c.
- Deleting the ith character from both the strings costs d.
The task is to find the minimum cost to make both the strings equal in configuration.
Examples:
Input: s1 = “121”, s2 = “223”, a = 2, b = 3, c = 4, d = 10
Output: 6
Change the first character from ‘1’ to ‘2’ which costs 2.
Change the third character from ‘3’ to ‘1’ which costs 4.
Input: s1 = ‘222’, s2 = ‘111’, a = 20, b = 30, c = 40, d = 1
Output: 3
Delete all characters which costs 3 which is the minimum possible.
Approach:
- Iterate in the string, and if s1[i] = s2[i] then perform no operation.
- If the s1[i] = ‘1’ and s2[i] = ‘2’ then perform the minimum cost operation from the following:
- Delete s1[i] and s2[i] which costs d.
- Change ‘1’ to ‘2’ which costs a
- Change ‘1’ to ‘3’ and then ‘3’ to ‘2’ which costs b + c.
- If the s1[i] = ‘2’ and s2[i] = ‘3’ then perform the minimum cost operation from the following:
- Delete s1[i] and s2[i] which costs d.
- Change ‘2’ to ‘3’ which costs b.
- Change ‘2’ to ‘1’ and then ‘1’ to ‘3’ which costs a + c.
- If the s1[i] = ‘3’ and s2[i] = ‘1’ then perform the minimum cost operation from the following:
- Delete s1[i] and s2[i] which costs d.
- Change ‘3’ to ‘1’ which costs c.
- Change ‘3’ to ‘2’ and then ‘2’ to ‘1’ which costs b + a.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; // Function to return the minimum cost to make the // configuration of both the strings same int findCost(string s1, string s2, int a, int b, int c, int d, int n) { int cost = 0; // Iterate and find the cost for ( int i = 0; i < n; i++) { if (s1[i] == s2[i]) continue ; else { // Find the minimum cost if ((s1[i] == '1' && s2[i] == '2' ) || (s2[i] == '1' && s1[i] == '2' )) cost += min(d, min(a, b + c)); else if ((s1[i] == '2' && s2[i] == '3' ) || (s2[i] == '2' && s1[i] == '3' )) cost += min(d, min(b, a + c)); else if ((s1[i] == '1' && s2[i] == '3' ) || (s2[i] == '1' && s1[i] == '3' )) cost += min(d, min(c, a + b)); } } return cost; } // Driver Code int main() { string s1 = "121" ; string s2 = "223" ; int a = 2, b = 3, c = 4, d = 10; int n = s1.size(); cout << findCost(s1, s2, a, b, c, d, n); return 0; } |
Java
// Java implementation of the approach class GFG { // Function to return the minimum cost to make the // configuration of both the strings same static int findCost(String s1, String s2, int a, int b, int c, int d, int n) { int cost = 0 ; // Iterate and find the cost for ( int i = 0 ; i < n; i++) { if (s1.charAt(i) == s2.charAt(i)) continue ; else { // Find the minimum cost if ((s1.charAt(i) == '1' && s2.charAt(i) == '2' ) || (s2.charAt(i) == '1' && s1.charAt(i) == '2' )) cost += Math.min(d, Math.min(a, b + c)); else if ((s1.charAt(i) == '2' && s2.charAt(i) == '3' ) || (s2.charAt(i) == '2' && s1.charAt(i) == '3' )) cost += Math.min(d, Math.min(b, a + c)); else if ((s1.charAt(i) == '1' && s2.charAt(i) == '3' ) || (s2.charAt(i) == '1' && s1.charAt(i) == '3' )) cost += Math.min(d, Math.min(c, a + b)); } } return cost; } // Driver Code public static void main(String[] args) { String s1 = "121" ; String s2 = "223" ; int a = 2 , b = 3 , c = 4 , d = 10 ; int n = s1.length(); System.out.println(findCost(s1, s2, a, b, c, d, n)); } } // This code is contributed by Code_Mech. |
Python3
# Python 3 implementation of the approach # Function to return the minimum cost to make # the configuration of both the strings same def findCost(s1, s2, a, b, c, d, n): cost = 0 # Iterate and find the cost for i in range (n): if (s1[i] = = s2[i]): continue else : # Find the minimum cost if ((s1[i] = = '1' and s2[i] = = '2' ) or (s2[i] = = '1' and s1[i] = = '2' )): cost + = min (d, min (a, b + c)) elif ((s1[i] = = '2' and s2[i] = = '3' ) or (s2[i] = = '2' and s1[i] = = '3' )): cost + = min (d, min (b, a + c)) elif ((s1[i] = = '1' and s2[i] = = '3' ) or (s2[i] = = '1' and s1[i] = = '3' )): cost + = min (d, min (c, a + b)) return cost # Driver Code if __name__ = = '__main__' : s1 = "121" s2 = "223" a = 2 b = 3 c = 4 d = 10 n = len (s1) print (findCost(s1, s2, a, b, c, d, n)) # This code is contributed by # Surendra_Gangwar |
C#
// C# implementation of the approach using System; class GFG { // Function to return the minimum cost to make the // configuration of both the strings same static int findCost( string s1, string s2, int a, int b, int c, int d, int n) { int cost = 0; // Iterate and find the cost for ( int i = 0; i < n; i++) { if (s1[i] == s2[i]) continue ; else { // Find the minimum cost if ((s1[i] == '1' && s2[i] == '2' ) || (s2[i] == '1' && s1[i] == '2' )) cost +=Math.Min(d,Math.Min(a, b + c)); else if ((s1[i] == '2' && s2[i] == '3' ) || (s2[i] == '2' && s1[i] == '3' )) cost +=Math.Min(d,Math.Min(b, a + c)); else if ((s1[i] == '1' && s2[i] == '3' ) || (s2[i] == '1' && s1[i] == '3' )) cost +=Math.Min(d,Math.Min(c, a + b)); } } return cost; } // Driver Code public static void Main() { string s1 = "121" ; string s2 = "223" ; int a = 2, b = 3, c = 4, d = 10; int n = s1.Length; Console.WriteLine(findCost(s1, s2, a, b, c, d, n)); } } // This Code is Contributed by Code_Mech. |
Javascript
<script> // javascript implementation of the approach // Function to return the minimum cost to make the // configuration of both the strings same function findCost( s1, s2 ,a, b, c, d, n) { var cost = 0; // Iterate and find the cost for ( var i = 0; i < n; i++) { if (s1[i] == s2[i]) continue ; else { // Find the minimum cost if ((s1[i] == '1' && s2[i] == '2' ) || (s2[i] == '1' && s1[i] == '2' )) cost +=Math.min(d,Math.min(a, b + c)); else if ((s1[i] == '2' && s2[i] == '3' ) || (s2[i] == '2' && s1[i] == '3' )) cost +=Math.min(d,Math.min(b, a + c)); else if ((s1[i] == '1' && s2[i] == '3' ) || (s2[i] == '1' && s1[i] == '3' )) cost +=Math.min(d,Math.min(c, a + b)); } } return cost; } // Driver Code var s1 = "121" ; var s2 = "223" ; var a = 2, b = 3, c = 4, d = 10; var n = s1.length; document.write(findCost(s1, s2, a, b, c, d, n)); // This code is contributed by bunnyram19. </script> |
6
Time Complexity: O(N), as we are using a loop to traverse N times. Where N is the length of the string.
Auxiliary Space: O(1), as we are not using any extra space.