Given two strings str1 and str2, the task is to find the minimum number of operations required to map each character of the string str1 to K ( < 1000) similar characters of the string str2 by either inserting a character into str2 or by removing a character from str2.
Examples:
Input: str1 = “aab”, str2 = “aaaabb”
Output: 0
Explanation:
Map {str2[0], str2[1]} to str1[0]
Map {str2[2], str2[3]} to str1[1].
Map {str2[4], str2[5]} to str1[2]
Since no operations are required to map each character of str1 to K(= 2) similar characters of str2.
Therefore, the required output is 0.Input: str1 = “aaa”, str2 = “bbb”
Output: 6
Explanation:
Removing str2[0], str2[1], str2[2] and inserting “aaa” modifies str2 to “aaa”.
Map { str2[0] } to str1[0], str2[1] to str1[1] and {str2[2]} to str1[2].
Therefore, the required output is 6.
Approach: To solve this problem, select the best value of K such that the number of operations required is minimum. To select the optimal value of K, iterate over all possible values of K and keep a track of the count of operations required for each of them. Finally, print the minimum count obtained. Follow the steps below to solve the problem:
- Initialize two arrays, say a1[] and a2[], to store the frequency of each distinct character of str1 and str2 respectively.
- Iterate over all possible values of K and keep a track of minimum till now in ans:
- Iterate over the range [0, 25] and check the following conditions:
- If a character is not present in str1 and present in str2, then all these characters should be removed from str2. Hence, the count should be updated accordingly.
- If a character is present in str1, then update the count by the absolute difference of frequency of that character in str2 and the current value of K multiplied by the frequency of that character in str1.
- Update the ans with the count.
- Iterate over the range [0, 25] and check the following conditions:
- Finally, print the count obtained, i.e. ans
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 minimum count of operations// required to map each character of str1 to K// same characters of str2int minOperations(string str1, string str2){ // Store frequency of each // distinct character of str1 int a1[26] = { 0 }; // Store frequency of each // distinct character of str2 int a2[26] = { 0 }; // Iterate over each character // of the string, str1 for (auto x : str1) { // Update frequency of // current character a1[x - 'a']++; } // Iterate over each character // of the string, str2 for (auto x : str2) { // Update frequency of // current character a2[x - 'a']++; } // Stores minimum count of operations // required to map each character of // str1 to K same characters of str2 int ans = INT_MAX; // Iterate over all // possible values of K for (int k = 1; k < 1001; k++) { // Stores count of operations required // to map each character of str1 to k // same characters of str2 int count = 0; // Iterate over possible characters for (int i = 0; i < 26; i++) { // If (i + 'a') is not // present in str1 if (a1[i] == 0) { // Update count by removing // character from str2 count += a2[i]; } // If a character is // present in str1 else { // Update count by inserting // character into str2 count += abs(a1[i] * k - a2[i]); } } // Update the answer ans = min(ans, count); } return ans;}// Driver Codeint main(){ string str1 = "aaa"; string str2 = "bbb"; // Function Call cout << minOperations(str1, str2) << endl; return 0;} |
Java
// Java program for the above approachclass GFG{ // Function to find minimum count of operations // required to map each character of str1 to K // same characters of str2 static int minOperations(String str1, String str2) { // Store frequency of each // distinct character of str1 int[] a1 = new int[26]; // Store frequency of each // distinct character of str2 int[] a2 = new int[26]; // Iterate over each character // of the string, str1 for (int x = 0; x < str1.length(); x++) { // Update frequency of // current character a1[str1.charAt(x) - 'a']++; } // Iterate over each character // of the string, str2 for (int x = 0; x < str2.length(); x++) { // Update frequency of // current character a2[str2.charAt(x) - 'a']++; } // Stores minimum count of operations // required to map each character of // str1 to K same characters of str2 int ans = Integer.MAX_VALUE; // Iterate over all // possible values of K for (int k = 1; k < 1001; k++) { // Stores count of operations required // to map each character of str1 to k // same characters of str2 int count = 0; // Iterate over possible characters for (int i = 0; i < 26; i++) { // If (i + 'a') is not // present in str1 if (a1[i] == 0) { // Update count by removing // character from str2 count += a2[i]; } // If a character is // present in str1 else { // Update count by inserting // character into str2 count += Math.abs(a1[i] * k - a2[i]); } } // Update the answer ans = Math.min(ans, count); } return ans; } // Driver code public static void main(String[] args) { String str1 = "aaa"; String str2 = "bbb"; // Function Call System.out.println(minOperations(str1, str2)); }}// This code is contributed by divyeshrabadiya07 |
Python3
# Python program for the above approach# Function to find minimum count of operations# required to map each character of str1 to K# same characters of str2import sysdef minOperations(str1, str2): # Store frequency of each # distinct character of str1 a1 = [0] * 26; # Store frequency of each # distinct character of str2 a2 = [0] * 26; # Iterate over each character # of the string, str1 for x in range(len(str1)): # Update frequency of # current character a1[ord(str1[x]) - ord('a')] += 1; # Iterate over each character # of the string, str2 for x in range(len(str2)): # Update frequency of # current character a2[ord(str2[x]) - ord('a')] += 1; # Stores minimum count of operations # required to map each character of # str1 to K same characters of str2 ans = sys.maxsize; # Iterate over all # possible values of K for k in range(1, 1001): # Stores count of operations required # to map each character of str1 to k # same characters of str2 count = 0; # Iterate over possible characters for i in range(26): # If (i + 'a') is not # present in str1 if (a1[i] == 0): # Update count by removing # character from str2 count += a2[i]; # If a character is # present in str1 else: # Update count by inserting # character into str2 count += abs(a1[i] * k - a2[i]); # Update the answer ans = min(ans, count); return ans;# Driver codeif __name__ == '__main__': str1 = "aaa"; str2 = "bbb"; # Function Call print(minOperations(str1, str2));# This code is contributed by 29AjayKumar |
C#
// C# program for the above approachusing System;class GFG{ // Function to find minimum count of operations // required to map each character of str1 to K // same characters of str2 static int minOperations(string str1, string str2) { // Store frequency of each // distinct character of str1 int[] a1 = new int[26]; // Store frequency of each // distinct character of str2 int[] a2 = new int[26]; // Iterate over each character // of the string, str1 foreach(char x in str1) { // Update frequency of // current character a1[x - 'a']++; } // Iterate over each character // of the string, str2 foreach(char x in str2) { // Update frequency of // current character a2[x - 'a']++; } // Stores minimum count of operations // required to map each character of // str1 to K same characters of str2 int ans = Int32.MaxValue; // Iterate over all // possible values of K for(int k = 1; k < 1001; k++) { // Stores count of operations required // to map each character of str1 to k // same characters of str2 int count = 0; // Iterate over possible characters for(int i = 0; i < 26; i++) { // If (i + 'a') is not // present in str1 if (a1[i] == 0) { // Update count by removing // character from str2 count += a2[i]; } // If a character is // present in str1 else { // Update count by inserting // character into str2 count += Math.Abs(a1[i] * k - a2[i]); } } // Update the answer ans = Math.Min(ans, count); } return ans; } // Driver code static void Main() { string str1 = "aaa"; string str2 = "bbb"; // Function Call Console.WriteLine(minOperations(str1, str2));}}// This code is contributed by divyesh072019 |
Javascript
<script> // Javascript program for the above approach // Function to find minimum count of operations // required to map each character of str1 to K // same characters of str2 function minOperations(str1, str2) { // Store frequency of each // distinct character of str1 let a1 = new Array(26); a1.fill(0); // Store frequency of each // distinct character of str2 let a2 = new Array(26); a2.fill(0); // Iterate over each character // of the string, str1 for(let x = 0; x < str1.length; x++) { // Update frequency of // current character a1[str1[x].charCodeAt() - 'a'.charCodeAt()]++; } // Iterate over each character // of the string, str2 for(let x = 0; x < str2.length; x++) { // Update frequency of // current character a2[str2[x].charCodeAt() - 'a'.charCodeAt()]++; } // Stores minimum count of operations // required to map each character of // str1 to K same characters of str2 let ans = Number.MAX_VALUE; // Iterate over all // possible values of K for(let k = 1; k < 1001; k++) { // Stores count of operations required // to map each character of str1 to k // same characters of str2 let count = 0; // Iterate over possible characters for(let i = 0; i < 26; i++) { // If (i + 'a') is not // present in str1 if (a1[i] == 0) { // Update count by removing // character from str2 count += a2[i]; } // If a character is // present in str1 else { // Update count by inserting // character into str2 count += Math.abs(a1[i] * k - a2[i]); } } // Update the answer ans = Math.min(ans, count); } return ans; } let str1 = "aaa"; let str2 = "bbb"; // Function Call document.write(minOperations(str1, str2)); </script> |
Output:
6
Time Complexity: O(N + 26 * K)
Auxiliary Space: O(1) as constant size array a1 and a2 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!
