Given two strings A and B of length N and M respectively, the task is to find the minimum cost to convert string A to B using the following operations:
- A character of string A can be swapped from another character of the same string. Cost = 0.
- A character can be deleted from string B or can be inserted in the string A. Cost = 1.
Examples:
Input: A = “1aB+-“, B = “CC”
Output: 7
Explanation: Remove all 5 characters from string A and insert character C twice. Therefore, the total cost = 5 + 2 = 7.Input: A = “aBcD”, B = “DBac”
Output: 0
Explanation: Following operations need to be performed to convert string A to string B:
- Swap ‘a’ with ‘D’. Therefore, A = “DBca”.
- Swap ‘a’ with ‘c’. Therefore, A = “DBac”.
Therefore, the total cost = 0.
Approach: The idea is to perform a swap operation maximum number of times to reduce the total cost. Observe that the characters which are common between the strings A and B can be swapped any number of times in A to make the string equal to B. All the characters that are present in the string A but not in the string B have to be deleted from A and all the characters present in B and not present in A have to be inserted in A to make both the strings equal. Follow the steps below to solve the problem:
- Initialize two arrays a[] and b[] of length 256 to store the frequencies of each character in the strings A and B respectively.
- Initialize a variable, say minCost, to store the minimum cost.
- Traverse over the range [0, 255] using the variable i and at each iteration, increment minCost by abs(a[i] – b[i]).
- After completing the above steps, print the value of minCost as the minimum cost required to convert string A to B.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the minimum cost// to convert string a to bvoid minimumCost(string a, string b){ // Stores the frequency of string // a and b respectively vector<int> fre1(256), fre2(256); // Store the frequencies of // characters in a for (char c : a) fre1[(int)(c)]++; // Store the frequencies of // characters in b for (char c : b) fre2[(int)(c)]++; // Minimum cost to convert A to B int mincost = 0; // Find the minimum cost for (int i = 0; i < 256; i++) { mincost += abs(fre1[i] - fre2[i]); } // Print the minimum cost cout << mincost << endl;}// Driver Codeint main(){ string A = "1AB+-", B = "cc"; // Function Call minimumCost(A, B); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{ // Function to find the minimum cost// to convert string a to bpublic static void minimumCost(String a, String b){ // Stores the frequency of string // a and b respectively int fre1[] = new int[256]; int fre2[] = new int[256]; // Store the frequencies of // characters in a for(char c : a.toCharArray()) fre1[(int)(c)]++; // Store the frequencies of // characters in b for(char c : b.toCharArray()) fre2[(int)(c)]++; // Minimum cost to convert A to B int mincost = 0; // Find the minimum cost for(int i = 0; i < 256; i++) { mincost += Math.abs(fre1[i] - fre2[i]); } // Print the minimum cost System.out.println(mincost);}// Driver Codepublic static void main(String[] args){ String A = "1AB+-", B = "cc"; // Function Call minimumCost(A, B);}}// This code is contributed by divyeshrabadiya07 |
Python3
# Python3 program for the above approach# Function to find the minimum cost# to convert a to bdef minimumCost(a, b): # Stores the frequency of string # a and b respectively fre1 = [0]*(256) fre2 = [0]*(256) # Store the frequencies of # characters in a for c in a: fre1[ord(c)] += 1 # Store the frequencies of # characters in b for c in b: fre2[ord(c)] += 1 # Minimum cost to convert A to B mincost = 0 # Find the minimum cost for i in range(256): mincost += abs(fre1[i] - fre2[i]) # Print the minimum cost print(mincost)# Driver Codeif __name__ == '__main__': A = "1AB+-" B = "cc" # Function Call minimumCost(A, B)# This code is contributed by mohit kumar 29 |
C#
// C# program for the above approachusing System; using System.Collections.Generic; class GFG{ // Function to find the minimum cost// to convert string a to bpublic static void minimumCost(string a, string b){ // Stores the frequency of string // a and b respectively int[] fre1 = new int[256]; int[] fre2 = new int[256]; // Store the frequencies of // characters in a foreach(char c in a.ToCharArray()) fre1[(int)(c)]++; // Store the frequencies of // characters in b foreach(char c in b.ToCharArray()) fre2[(int)(c)]++; // Minimum cost to convert A to B int mincost = 0; // Find the minimum cost for(int i = 0; i < 256; i++) { mincost += Math.Abs(fre1[i] - fre2[i]); } // Print the minimum cost Console.Write(mincost);} // Driver code public static void Main() { string A = "1AB+-", B = "cc"; // Function Call minimumCost(A, B);} }// This code is contributed by sanjoy_62 |
Javascript
<script>// Javascript program for the above approach// Function to find the minimum cost// to convert string a to bfunction minimumCost(a, b){ // Stores the frequency of string // a and b respectively var fre1 = Array(256).fill(0), fre2= Array(256).fill(0); // Store the frequencies of // characters in a a.split('').forEach(c => { fre1[c.charCodeAt(0)]++; }); // Store the frequencies of // characters in b b.split('').forEach(c => { fre2[c.charCodeAt(0)]++; }); // Minimum cost to convert A to B var mincost = 0; // Find the minimum cost for (var i = 0; i < 256; i++) { mincost += Math.abs(fre1[i] - fre2[i]); } // Print the minimum cost document.write( mincost );}// Driver Codevar A = "1AB+-", B = "cc";// Function CallminimumCost(A, B);// This code is contributed by importantly.</script> |
Output:
7
Time Complexity: O(N + M)
Auxiliary Space: O(1) because constant size arrays fre1 and fre2 are used
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
