Número mínimo de manipulaciones requeridas para hacer dos anagramas de strings sin eliminación de caracteres | conjunto 2

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énticos

Entrada: 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:
  • 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>
Producción

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *