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