Dadas dos strings A y B de longitud N y M respectivamente, la tarea es encontrar el costo mínimo para convertir la string A en B usando las siguientes operaciones:
- Un carácter de la string A puede intercambiarse con otro carácter de la misma string. Costo = 0 .
- Se puede eliminar un carácter de la string B o se puede insertar en la string A. Costo = 1 .
Ejemplos:
Entrada: A = “1aB+-“, B = “CC”
Salida: 7
Explicación: elimine los 5 caracteres de la string A e inserte el carácter C dos veces. Por lo tanto, el costo total = 5 + 2 = 7.Entrada: A = “aBcD”, B = “DBac”
Salida: 0
Explicación: Es necesario realizar las siguientes operaciones para convertir la string A en la string B:
- Cambia ‘a’ por ‘D’. Por lo tanto, A = “DBca”.
- Cambia ‘a’ por ‘c’. Por lo tanto, A = “DBac”.<
Por lo tanto, el costo total = 0.
Enfoque: La idea es realizar una operación de intercambio el máximo número de veces para reducir el costo total. Observe que los caracteres que son comunes entre las strings A y B se pueden intercambiar cualquier número de veces en A para hacer que la string sea igual a B. Todos los caracteres que están presentes en la string A pero no en la string B deben eliminarse de A y todos los caracteres presentes en B y no presentes en A deben insertarse en A para que ambas strings sean iguales. Siga los pasos a continuación para resolver el problema:
- Inicialice dos arrays a[] y b[] de longitud 256 para almacenar las frecuencias de cada carácter en las strings A y B respectivamente.
- Inicialice una variable, digamos minCost , para almacenar el costo mínimo.
- Recorra el rango [0, 255] usando la variable i y en cada iteración, incremente minCost por abs(a[i] – b[i]) .
- Después de completar los pasos anteriores, imprima el valor de minCost como el costo mínimo requerido para convertir la string A en B.
A continuación se muestra la implementación del enfoque anterior:
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 b
void 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 Code
int main()
{
string A = "1AB+-", B = "cc";
// Function Call
minimumCost(A, B);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to find the minimum cost
// to convert string a to b
public 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 Code
public 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 b def 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 Code if __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 approach
using System;
using System.Collections.Generic;
class GFG{
// Function to find the minimum cost
// to convert string a to b
public 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 b
function 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 Code
var A = "1AB+-", B = "cc";
// Function Call
minimumCost(A, B);
// This code is contributed by importantly.
</script>
7
Complejidad temporal: O(N + M)
Espacio auxiliar: O(N + M)
Publicación traducida automáticamente
Artículo escrito por grand_master y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA