Dadas dos strings str1 y str2 , la tarea es contar el número mínimo de operaciones de los siguientes tres tipos en una de las dos strings que se requieren para hacer permutaciones entre str1 y str2 :
- Inserta un carácter en la string.
- Eliminar un carácter de la string.
- Reemplace un carácter con otro carácter de la string.
Nota: Todas las operaciones anteriores son de igual costo.
Ejemplos:
Entrada: str1 = “geeksforgeeks”, str2 = “geeksforcoder”
Salida: 4
Explicación: Reorganice la string str2 a “geeksforcedor”
Reemplace el valor de str1[8] a ‘c’.
Reemplace el valor de str1[10] a ‘d’.
Reemplace el valor de str1[11] a ‘o’.
Reemplace el valor de str1[12] a ‘r’.
Por lo tanto, la salida requerida es 4.Entrada: str1 = «geeks», str2 = «keeg»
Salida: 1
Enfoque: el problema se puede resolver utilizando Hashing para almacenar la frecuencia de cada carácter de la string. A continuación se presentan las observaciones para resolver el problema:
X = Número de caracteres que están presentes en ambas strings, str1 y str2.
N1 – X = Número de caracteres presentes solo en str1.
N2 – X = Número de caracteres presentes solo en str2.
Número total de operaciones de reemplazo = min(N1 – X, N2 – X)
Número total de operaciones de inserción/eliminación = max(N1 – X, N2 – X) – min(N1 – X, N2 – X).
Por lo tanto, número total de operaciones = max(N1 – X, N2 – X),
Siga los pasos a continuación para resolver el problema:
- Inicialice dos arrays, digamos freq1[] y freq2[] para almacenar la frecuencia de todos los caracteres de str1 y str2 respectivamente.
- Recorra ambas strings y almacene la frecuencia de cada carácter de ambas strings en las arrays freq1[] y freq2[] respectivamente.
- Atraviese las arrays freq1[] y freq2[] .
- Para cada i -ésimo carácter, si freq1[i] excede freq2[i] , entonces reemplace freq1[i] por freq1[i] – freq2[i] y establezca freq2[i] = 0 y viceversa.
- Finalmente, calcule la suma de las arrays freq1[] y freq2[] , e imprima el máximo entre ellas como respuesta
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 minimize the count of
// operations to make str1 and str2
// permutations of each other
int ctMinEdits(string str1, string str2)
{
int N1 = str1.length();
int N2 = str2.length();
// Store the frequency of
// each character of str1
int freq1[256] = { 0 };
for (int i = 0; i < N1; i++) {
freq1[str1[i]]++;
}
// Store the frequency of
// each character of str2
int freq2[256] = { 0 };
for (int i = 0; i < N2; i++) {
freq2[str2[i]]++;
}
// Traverse the freq1[] and freq2[]
for (int i = 0; i < 256; i++) {
// If frequency of character in
// str1 is greater than str2
if (freq1[i] > freq2[i]) {
freq1[i] = freq1[i]
- freq2[i];
freq2[i] = 0;
}
// Otherwise
else {
freq2[i] = freq2[i]
- freq1[i];
freq1[i] = 0;
}
}
// Store sum of freq1[]
int sum1 = 0;
// Store sum of freq2[]
int sum2 = 0;
for (int i = 0; i < 256; i++) {
sum1 += freq1[i];
sum2 += freq2[i];
}
return max(sum1, sum2);
}
// Driver Code
int main()
{
string str1 = "geeksforgeeks";
string str2 = "geeksforcoder";
cout << ctMinEdits(str1, str2);
}
Java
// Java program to implement
// the above approach
import java.util.*;
import java.io.*;
import java.lang.Math;
class GFG{
// Function to minimize the count of
// operations to make str1 and str2
// permutations of each other
static int ctMinEdits(String str1, String str2)
{
int N1 = str1.length();
int N2 = str2.length();
// Store the frequency of
// each character of str1
int freq1[] = new int[256];
Arrays.fill(freq1, 0);
for(int i = 0; i < N1; i++)
{
freq1[str1.charAt(i)]++;
}
// Store the frequency of
// each character of str2
int freq2[] = new int[256];
Arrays.fill(freq2, 0);
for(int i = 0; i < N2; i++)
{
freq2[str2.charAt(i)]++;
}
// Traverse the freq1[] and freq2[]
for(int i = 0; i < 256; i++)
{
// If frequency of character in
// str1 is greater than str2
if (freq1[i] > freq2[i])
{
freq1[i] = freq1[i] - freq2[i];
freq2[i] = 0;
}
// Otherwise
else
{
freq2[i] = freq2[i] - freq1[i];
freq1[i] = 0;
}
}
// Store sum of freq1[]
int sum1 = 0;
// Store sum of freq2[]
int sum2 = 0;
for(int i = 0; i < 256; i++)
{
sum1 += freq1[i];
sum2 += freq2[i];
}
return Math.max(sum1, sum2);
}
// Driver Code
public static void main(final String[] args)
{
String str1 = "geeksforgeeks";
String str2 = "geeksforcoder";
System.out.println(ctMinEdits(str1, str2));
}
}
// This code is contributed by bikram2001jha
Python3
# Python3 program to implement # the above approach # Function to minimize the count of # operations to make str1 and str2 # permutations of each other def ctMinEdits(str1, str2): N1 = len(str1) N2 = len(str2) # Store the frequency of # each character of str1 freq1 = [0] * 256 for i in range(N1): freq1[ord(str1[i])] += 1 # Store the frequency of # each character of str2 freq2 = [0] * 256 for i in range(N2): freq2[ord(str2[i])] += 1 # Traverse the freq1[] and freq2[] for i in range(256): # If frequency of character in # str1 is greater than str2 if (freq1[i] > freq2[i]): freq1[i] = freq1[i] - freq2[i] freq2[i] = 0 # Otherwise else: freq2[i] = freq2[i] - freq1[i] freq1[i] = 0 # Store sum of freq1[] sum1 = 0 # Store sum of freq2[] sum2 = 0 for i in range(256): sum1 += freq1[i] sum2 += freq2[i] return max(sum1, sum2) # Driver Code str1 = "geeksforgeeks" str2 = "geeksforcoder" print(ctMinEdits(str1, str2)) # This code is contributed by code_hunt
C#
// C# program to implement
// the above approach
using System;
class GFG{
// Function to minimize the count of
// operations to make str1 and str2
// permutations of each other
static int ctMinEdits(string str1, string str2)
{
int N1 = str1.Length;
int N2 = str2.Length;
// Store the frequency of
// each character of str1
int[] freq1 = new int[256];
freq1[0] = str1[0];
for(int i = 0; i < N1; i++)
{
freq1[str1[i]]++;
}
// Store the frequency of
// each character of str2
int[] freq2 = new int[256];
freq2[0] = str2[0];
for(int i = 0; i < N2; i++)
{
freq2[str2[i]]++;
}
// Traverse the freq1[] and freq2[]
for(int i = 0; i < 256; i++)
{
// If frequency of character in
// str1 is greater than str2
if (freq1[i] > freq2[i])
{
freq1[i] = freq1[i] - freq2[i];
freq2[i] = 0;
}
// Otherwise
else
{
freq2[i] = freq2[i] - freq1[i];
freq1[i] = 0;
}
}
// Store sum of freq1[]
int sum1 = 0;
// Store sum of freq2[]
int sum2 = 0;
for(int i = 0; i < 256; i++)
{
sum1 += freq1[i];
sum2 += freq2[i];
}
return Math.Max(sum1, sum2);
}
// Driver Code
public static void Main()
{
string str1 = "geeksforgeeks";
string str2 = "geeksforcoder";
Console.WriteLine(ctMinEdits(str1, str2));
}
}
// This code is contributed by code_hunt
Javascript
<script>
// Javascript program to implement
// the above approach
// Function to minimize the count of
// operations to make str1 and str2
// permutations of each other
function ctMinEdits(str1, str2)
{
let N1 = str1.length;
let N2 = str2.length;
// Store the frequency of
// each character of str1
let freq1 = new Array(256).fill(0);
for(let i = 0; i < N1; i++)
{
freq1[str1[i].charCodeAt()]++;
}
// Store the frequency of
// each character of str2
let freq2 = new Array(256).fill(0);
for(let i = 0; i < N2; i++)
{
freq2[str2[i].charCodeAt()]++;
}
// Traverse the freq1[] and freq2[]
for(let i = 0; i < 256; i++)
{
// If frequency of character in
// str1 is greater than str2
if (freq1[i] > freq2[i])
{
freq1[i] = freq1[i] - freq2[i];
freq2[i] = 0;
}
// Otherwise
else
{
freq2[i] = freq2[i] - freq1[i];
freq1[i] = 0;
}
}
// Store sum of freq1[]
let sum1 = 0;
// Store sum of freq2[]
let sum2 = 0;
for(let i = 0; i < 256; i++)
{
sum1 += freq1[i];
sum2 += freq2[i];
}
return Math.max(sum1, sum2);
}
// Driver Code
let str1 = "geeksforgeeks";
let str2 = "geeksforcoder";
document.write(ctMinEdits(str1.split(''), str2.split('')));
</script>
Producción:
4
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por rohitprasadswn y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA