Make all strings from a given array equal by replacing minimum number of characters
Given an array of equal-length strings arr[], the task is to make all the strings of the array equal by replacing any character of a string with any other character, minimum number of times.
Examples:
Input: arr[] = { “west”, “east”, “wait” }
Output: 3
Explanation:
Replacing arr[0][1] with ‘a’ modifies arr[] to { “west”, “east”, “wait” }.
Replacing arr[1][0] with ‘w’ modifies arr[] to { “wast”, “wast”, “wait” }.
Replacing arr[2][2] with ‘s’ modifies arr[] to { “wast”, “wast”, “wast” }.
Therefore, the required output is 3.Input: arr[] = { “abcd”, “bcde”, “cdef” }
Output: 8
Approach: The problem can be solved using Hashing. Follow the steps below to solve the problem:
- Initialize a 2D array, say hash[][], where hash[i][j] stores the frequency of the character i present at the jth index of all the strings.
- Traverse the array arr[] using variable i. For every ith string encountered, count the frequency of each distinct character of the string and store it into the hash[][] array.
- Initialize a variable, say cntMinOp, to store the minimum count of operations required to make all the strings of the array equal.
- Traverse the array hash[][] using variable i. For every ith column encountered, calculate the sum of the column, say Sum, the maximum element in the column, say Max, and update cntMinOp += (Sum – Max).
- Finally, print the value of cntMinOp.
Below is the implementation of the above approach:
C++
// C++ program to implement // the above approach #include <bits/stdc++.h> using namespace std; // Function to find the minimum count of // operations required to make all strings // equal by replacing characters of strings int minOperation(string arr[], int N) { // Stores minimum count of operations // required to make all strings equal int cntMinOP = 0; // Stores length of the string int M = arr[0].length(); // hash[i][j]: Stores frequency of character // i present at j-th index of all strings int hash[256][M]; // Initialize hash[][] to 0 memset (hash, 0, sizeof (hash)); // Traverse the array arr[] for ( int i = 0; i < N; i++) { // Iterate over characters of // current string for ( int j = 0; j < M; j++) { // Update frequency of // arr[i][j] hash[arr[i][j]][j]++; } } // Traverse hash[][] array for ( int i = 0; i < M; i++) { // Stores sum of i-th column int Sum = 0; // Stores the largest element // of i-th column int Max = 0; // Iterate over all possible // characters for ( int j = 0; j < 256; j++) { // Update Sum Sum += hash[j][i]; // Update Max Max = max(Max, hash[j][i]); } // Update cntMinOP cntMinOP += (Sum - Max); } return cntMinOP; } // Driver Code int main() { string arr[] = { "abcd" , "bcde" , "cdef" }; int N = sizeof (arr) / sizeof (arr[0]); // Function call cout << minOperation(arr, N) << "\n" ; } |
Java
// Java program to implement // the above approach import java.util.*; class GFG { // Function to find the minimum count of // operations required to make all Strings // equal by replacing characters of Strings static int minOperation(String arr[], int N) { // Stores minimum count of operations // required to make all Strings equal int cntMinOP = 0 ; // Stores length of the String int M = arr[ 0 ].length(); // hash[i][j]: Stores frequency of character // i present at j-th index of all Strings int [][]hash = new int [ 256 ][M]; // Traverse the array arr[] for ( int i = 0 ; i < N; i++) { // Iterate over characters of // current String for ( int j = 0 ; j < M; j++) { // Update frequency of // arr[i][j] hash[arr[i].charAt(j)][j]++; } } // Traverse hash[][] array for ( int i = 0 ; i < M; i++) { // Stores sum of i-th column int Sum = 0 ; // Stores the largest element // of i-th column int Max = 0 ; // Iterate over all possible // characters for ( int j = 0 ; j < 256 ; j++) { // Update Sum Sum += hash[j][i]; // Update Max Max = Math.max(Max, hash[j][i]); } // Update cntMinOP cntMinOP += (Sum - Max); } return cntMinOP; } // Driver Code public static void main(String[] args) { String arr[] = { "abcd" , "bcde" , "cdef" }; int N = arr.length; // Function call System.out.print(minOperation(arr, N)+ "\n" ); } } // This code is contributed by shikhasingrajput |
Python3
# Python program to implement # the above approach # Function to find the minimum count of # operations required to make all Strings # equal by replacing characters of Strings def minOperation(arr, N): # Stores minimum count of operations # required to make all Strings equal cntMinOP = 0 ; # Stores length of the String M = len (arr[ 0 ]); # hash[i][j]: Stores frequency of character # i present at j-th index of all Strings hash = [[ 0 for i in range (M)] for j in range ( 256 )]; # Traverse the array arr for i in range (N): # Iterate over characters of # current String for j in range (M): # Update frequency of # arr[i][j] hash [ ord (arr[i][j])][j] + = 1 ; # Traverse hash array for i in range (M): # Stores sum of i-th column Sum = 0 ; # Stores the largest element # of i-th column Max = 0 ; # Iterate over all possible # characters for j in range ( 256 ): # Update Sum Sum + = hash [j][i]; # Update Max Max = max ( Max , hash [j][i]); # Update cntMinOP cntMinOP + = ( Sum - Max ); return cntMinOP; # Driver Code if __name__ = = '__main__' : arr = [ "abcd" , "bcde" , "cdef" ]; N = len (arr); # Function call print (minOperation(arr, N)); # This code is contributed by 29AjayKumar |
C#
// C# program to implement // the above approach using System; class GFG { // Function to find the minimum count of // operations required to make all Strings // equal by replacing characters of Strings static int minOperation(String []arr, int N) { // Stores minimum count of operations // required to make all Strings equal int cntMinOP = 0; // Stores length of the String int M = arr[0].Length; // hash[i,j]: Stores frequency of character // i present at j-th index of all Strings int [,]hash = new int [256, M]; // Traverse the array []arr for ( int i = 0; i < N; i++) { // Iterate over characters of // current String for ( int j = 0; j < M; j++) { // Update frequency of // arr[i,j] hash[arr[i][j], j]++; } } // Traverse hash[,] array for ( int i = 0; i < M; i++) { // Stores sum of i-th column int Sum = 0; // Stores the largest element // of i-th column int Max = 0; // Iterate over all possible // characters for ( int j = 0; j < 256; j++) { // Update Sum Sum += hash[j, i]; // Update Max Max = Math.Max(Max, hash[j, i]); } // Update cntMinOP cntMinOP += (Sum - Max); } return cntMinOP; } // Driver Code public static void Main(String[] args) { String []arr = { "abcd" , "bcde" , "cdef" }; int N = arr.Length; // Function call Console.Write(minOperation(arr, N)+ "\n" ); } } // This code is contributed by 29AjayKumar |
Javascript
<script> // JavaScript program to implement // the above approach // Function to find the minimum count of // operations required to make all strings // equal by replacing characters of strings function minOperation(arr, N) { // Stores minimum count of operations // required to make all strings equal var cntMinOP = 0; // Stores length of the string var M = arr[0].length; // hash[i][j]: Stores frequency of character // i present at j-th index of all strings var hash = Array.from(Array(256), ()=>Array(M).fill(0)); // Traverse the array arr[] for ( var i = 0; i < N; i++) { // Iterate over characters of // current string for ( var j = 0; j < M; j++) { // Update frequency of // arr[i][j] hash[arr[i][j].charCodeAt(0)][j]++; } } // Traverse hash[][] array for ( var i = 0; i < M; i++) { // Stores sum of i-th column var Sum = 0; // Stores the largest element // of i-th column var Max = 0; // Iterate over all possible // characters for ( var j = 0; j < 256; j++) { // Update Sum Sum += hash[j][i]; // Update Max Max = Math.max(Max, hash[j][i]); } // Update cntMinOP cntMinOP += (Sum - Max); } return cntMinOP; } // Driver Code var arr = [ "abcd" , "bcde" , "cdef" ]; var N = arr.length; // Function call document.write( minOperation(arr, N) + "<br>" ); </script> |
8
Time Complexity:O(N * (M + 256)), where M is the length of the string
Auxiliary Space:O(M + 256)
Contact Us