Dadas dos strings de igual tamaño s[] y t[] de tamaño N . En un solo paso, elija cualquier carácter de t[] y reemplácelo con otro carácter. Devuelve el número mínimo de pasos para hacer t[] un anagrama de s[] .
Nota: un anagrama de una string es una string que contiene los mismos caracteres con un orden diferente (o el mismo).
Ejemplos:
Entrada: s = “baa”, t = “aba”
Salida: 0
Explicación: Ambas strings contienen caracteres idénticosEntrada: s = “ddcf”, t = “cedk”
Salida: 2
Explicación: Aquí, necesitamos cambiar dos caracteres en cualquiera de las strings para que sean idénticos. Podemos cambiar ‘d’ y ‘f’ en s1 o ‘e’ y ‘k’ en s2.
Enfoque hash: El enfoque hashing se ha discutido en el Conjunto 1 de este artículo . En este artículo, veremos cómo resolver este problema usando el mapa.
Enfoque: la idea es usar Hashing para almacenar las frecuencias de cada carácter de la string s[] y luego, mientras atraviesa la string t[] , verifique si ese carácter está presente en el mapa o no. En caso afirmativo, disminuya su valor en 1. De lo contrario, aumente el conteo en 1. Siga los pasos a continuación para resolver el problema:
- Inicialice la variable count como 0 para almacenar la respuesta.
- Inicialice un mapa_desordenado<char, int> a[] para almacenar las frecuencias.
- Iterar sobre el rango [0, N) usando la variable i y realizar los siguientes pasos:
- Aumenta el valor de a[i] en 1.
- Recorra la string usando la variable j y realice las siguientes tareas:
- Si a[j] es mayor que 0 , disminuya el valor de a[j] en 1.
- De lo contrario, aumente el valor de count en 1.
- Después de realizar los pasos anteriores, imprima el valor de conteo como respuesta.
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 count the minimum changes
// to make the 2 strings anagram
int minSteps(string s, string t)
{
unordered_map<char, int> a;
// For counting the steps to be changed
int count = 0;
for (auto i : s) {
// Increasing the count if the no.
// is present
a[i]++;
}
for (auto j : t) {
// Checking if the element of s is
// present in t or not
if (a[j] > 0) {
// If present than decrease the
// no. in map by 1
a[j]--;
}
else {
// If not present
// increase count by 1
count++;
}
}
cout << count;
// Return count
return count;
}
// Driver Code
int main()
{
string s = "ddcf", t = "cedk";
minSteps(s, t);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG {
// Function to count the minimum changes
// to make the 2 Strings anagram
static int minSteps(String s, String t) {
HashMap<Character, Integer> a =
new HashMap<Character, Integer>();
// For counting the steps to be changed
int count = 0;
for (char i : s.toCharArray()) {
// Increasing the count if the no.
// is present
if (a.containsKey(i)) {
a.put(i, a.get(i) + 1);
} else {
a.put(i, 1);
}
}
for (char j : t.toCharArray()) {
// Checking if the element of s is
// present in t or not
if (a.containsKey(j)) {
// If present than decrease the
// no. in map by 1
a.put(j, a.get(j) - 1);
} else {
// If not present
// increase count by 1
count++;
}
}
System.out.print(count);
// Return count
return count;
}
// Driver Code
public static void main(String[] args) {
String s = "ddcf", t = "cedk";
minSteps(s, t);
}
}
// This code is contributed by shikhasingrajput
Python3
# python program for the above approach
# Function to count the minimum changes
# to make the 2 strings anagram
def minSteps(s, t):
a = {}
# For counting the steps to be changed
count = 0
for i in s:
# Increasing the count if the no.
# is present
if i in a:
a[i] += 1
else:
a[i] = 1
for j in t:
# Checking if the element of s is
# present in t or not
if j in a:
# If present than decrease the
# no. in map by 1
a[j] -= 1
else:
# If not present
# increase count by 1
count += 1
print(count)
# Return count
return count
# Driver Code
if __name__ == "__main__":
s = "ddcf"
t = "cedk"
minSteps(s, t)
# This code is contributed by rakeshsahni
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
public class GFG {
// Function to count the minimum changes
// to make the 2 Strings anagram
static int minSteps(String s, String t) {
Dictionary<char, int> a =
new Dictionary<char, int>();
// For counting the steps to be changed
int count = 0;
foreach (char i in s.ToCharArray()) {
// Increasing the count if the no.
// is present
if (a.ContainsKey(i)) {
a[i] = a[i] + 1;
} else {
a.Add(i, 1);
}
}
foreach (char j in t.ToCharArray()) {
// Checking if the element of s is
// present in t or not
if (a.ContainsKey(j)) {
// If present than decrease the
// no. in map by 1
a[j] = a[j] - 1;
} else {
// If not present
// increase count by 1
count++;
}
}
Console.Write(count);
// Return count
return count;
}
// Driver Code
public static void Main(String[] args) {
String s = "ddcf", t = "cedk";
minSteps(s, t);
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// JavaScript Program to implement
// the above approach
// Function to count the minimum changes
// to make the 2 strings anagram
function minSteps(s, t)
{
let a = new Map();
// For counting the steps to be changed
let count = 0;
for (let i of s) {
// Increasing the count if the no.
// is present
if (a.has(i)) {
a.set(i, 1)
}
else {
a.set(i, a.get(i) + 1)
}
}
for (let j of t) {
// Checking if the element of s is
// present in t or not
if (a.has(j)) {
// If present than decrease the
// no. in map by 1
a.set(j, a.get(j) - 1);
}
else {
// If not present
// increase count by 1
count++;
}
}
document.write(count);
// Return count
return count;
}
// Driver Code
let s = "ddcf", t = "cedk";
minSteps(s, t);
// This code is contributed by Potta Lokesh
</script>
2
Complejidad de tiempo: O(N)
Espacio auxiliar: O(max(N, 26))
Publicación traducida automáticamente
Artículo escrito por durgeshsahu7 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA