Dada una array de strings de igual longitud arr[] , la tarea es hacer que todas las strings de la array sean iguales reemplazando cualquier carácter de una string con cualquier otro carácter, un número mínimo de veces.
Ejemplos:
Entrada: arr[] = { “oeste”, “este”, “esperar” }
Salida: 3
Explicación:
Reemplazar arr[0][1] con ‘a’ modifica arr[] a { “oeste”, “este”, «Espere» }.
Reemplazar arr[1][0] con ‘w’ modifica arr[] a { “wast”, “wast”, “wait” }.
Reemplazar arr[2][2] con ‘s’ modifica arr[] a { “wast”, “wast”, “wast” }.
Por lo tanto, la salida requerida es 3.Entrada: arr[] = { “abcd”, “bcde”, “cdef” }
Salida: 8
Enfoque: El problema se puede resolver usando Hashing . Siga los pasos a continuación para resolver el problema:
- Inicialice una array 2D , digamos hash[][] , donde hash[i][j] almacena la frecuencia del carácter que presento en el índice jth de todas las strings.
- Recorra la array arr[] usando la variable i . Para cada i- ésima string encontrada, cuente la frecuencia de cada carácter distinto de la string y guárdela en la array hash[][] .
- Inicialice una variable, digamos cntMinOp , para almacenar el recuento mínimo de operaciones requeridas para hacer que todas las strings de la array sean iguales.
- Recorra la array hash[][] usando la variable i . Para cada i- ésima columna encontrada, calcule la suma de la columna, digamos Sum , el elemento máximo en la columna, digamos Max , y actualice cntMinOp += (Sum – Max) .
- Finalmente, imprima el valor de cntMinOp .
A continuación se muestra la implementación del enfoque anterior:
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>
Producción:
8
Complejidad de tiempo: O(N * (M + 256)), donde M es la longitud de la string
Espacio auxiliar: O(M + 256)