Convierta la string X en un anagrama de la string Y con reemplazos mínimos

Dadas dos strings X e Y, necesitamos convertir la string X en un anagrama de la string Y con reemplazos mínimos. Si tenemos varias formas de lograr el objetivo, optamos por la string lexicográficamente más pequeña donde la longitud de cada string $\in [1, 100000]$

Ejemplos:

Input : X = "CDBABC" 
        Y = "ADCABD"
Output : Anagram : ADBADC
         Number of changes made: 2

Input : X = "PJPOJOVMAK"
        Y = "FVACRHLDAP"
Output : Anagram : ACPDFHVLAR
         Number of changes made: 7

Enfoque utilizado: tenemos que convertir la string X en un anagrama lexicográficamente más pequeño de la string Y haciendo reemplazos mínimos en la string original X. Mantenemos dos arrays de contadores que almacenan el conteo/frecuencia de cada carácter en las dos strings. Sean los contadores de las dos strings $Count_{x}$ y $Count_{y}$ . Ahora, los anagramas por definición significan que la frecuencia de los caracteres en dos anagramas es siempre igual. Por lo tanto, para convertir la string X en un anagrama de la string Y, la frecuencia de caracteres debe ser igual. Por lo tanto, el número total de alteraciones que necesitamos hacer para convertir la string X en un anagrama de la string Y es $(\sum |Count_{x_{i}} - Count_{y_{i}}|)/2$ , donde iteramos para cada carácter i .

La mitad del trabajo está hecho ya que sabemos cuántos reemplazos se deben hacer. Ahora necesitamos la string lexicográficamente más pequeña. Ahora, para una posición específica, buscamos todos los caracteres posibles de la ‘A’ a la ‘Z’ y verificamos para cada carácter si podría encajar en esta posición o ahora. Para una mejor comprensión, iteramos para cada posición en la string. Compruebe si hay un carácter que está en la string Y y no en la string X (o si la frecuencia del carácter es más en la string Y y menos en la string X). Ahora, si hay uno, verificamos que el carácter en la posición actual en X, ¿es innecesario? es decir, tiene más frecuencia en la string X y menos frecuencia en la string Y. Ahora, si todas las casillas están marcadas, verificamos si insertamos el carácter en esta posición, ya que necesitamos generar la string lexicográficamente más pequeña.

Implementación:

C++

// C++ program to convert string X to
// string Y which minimum number of changes.
#include <bits/stdc++.h>
using namespace std;
 
#define MAX 26
 
// Function that converts string X
// into lexicographically smallest
// anagram of string Y with minimal changes
void printAnagramAndChanges(string X, string Y)
{
    int countx[MAX] = {0}, county[MAX] = {0},
        ctrx[MAX] = {0}, ctry[MAX] = {0};
 
    int change = 0;
    int l = X.length();
 
    // Counting frequency of characters
    // in each string.
    for (int i = 0; i < l; i++) {
        countx[X[i] - 'A']++;
        county[Y[i] - 'A']++;
    }
 
    // We maintain two more counter arrays
    // ctrx[] and ctry[]
    // Ctrx[] maintains the count of extra
    // elements present in string X than
    // string Y
    // Ctry[] maintains the count of
    // characters missing from string X
    // which should be present in string Y.
    for (int i = 0; i < MAX; i++) {
        if (countx[i] > county[i])
            ctrx[i] += (countx[i] - county[i]);
        else if (countx[i] < county[i])
            ctry[i] += (county[i] - countx[i]);
        change += abs(county[i] - countx[i]);
    }
 
    for (int i = 0; i < l; i++) {
 
        // This means that we cannot edit the
        // current character as it's frequency
        // in string X is equal to or less
        // than the frequency in string Y.
        // Thus, we go to the next position
        if (ctrx[X[i] - 'A'] == 0)
            continue;
 
        // Here, we try to find that character,
        // which has more frequency in string Y
        // and less in string X. We try to find
        // this character in lexicographical
        // order so that we get
        // lexicographically smaller string
        int j;
        for (j = 0; j < MAX; j++)
            if ((ctry[j]) > 0)
                break;
 
        // This portion deals with the
        // lexicographical property.
        // Now, we put a character in string X
        // when either this character has smaller
        // value than the character present there
        // right now or if this is the last position
        // for it to exchange, else we fix the
        // character already present here in
        // this position.
        if (countx[X[i] - 'A'] == ctrx[X[i] - 'A']
            || X[i] - 'A' > j) {
 
            countx[X[i] - 'A']--;
            ctrx[X[i] - 'A']--;
            ctry[j]--;
            X[i] = 'A' + j;
        }
        else
            countx[X[i] - 'A']--;
    }
 
    cout << "Anagram : " << X << endl;
    cout << "Number of changes made : " << change / 2;
}
 
// Driver program
int main()
{
    string x = "CDBABC", y = "ADCABD";
    printAnagramAndChanges(x, y);
    return 0;
}

Java

// Java program to convert string X to
// string Y which minimum number of changes.
class GFG
{
 
    static final int MAX = 26;
 
    // Function that converts string X
    // into lexicographically smallest
    // anagram of string Y with minimal changes
    static void printAnagramAndChanges(char[] X,
                                        char[] Y)
    {
        int countx[] = new int[MAX], county[] = new int[MAX],
            ctrx[] = new int[MAX], ctry[] = new int[MAX];
 
        int change = 0;
        int l = X.length;
 
        // Counting frequency of characters
        // in each string.
        for (int i = 0; i < l; i++)
        {
            countx[X[i] - 'A']++;
            county[Y[i] - 'A']++;
        }
 
        // We maintain two more counter arrays
        // ctrx[] and ctry[]
        // Ctrx[] maintains the count of extra
        // elements present in string X than
        // string Y
        // Ctry[] maintains the count of
        // characters missing from string X
        // which should be present in string Y.
        for (int i = 0; i < MAX; i++)
        {
            if (countx[i] > county[i])
            {
                ctrx[i] += (countx[i] - county[i]);
            }
            else if (countx[i] < county[i])
            {
                ctry[i] += (county[i] - countx[i]);
            }
            change += Math.abs(county[i] - countx[i]);
        }
 
        for (int i = 0; i < l; i++)
        {
 
            // This means that we cannot edit the
            // current character as it's frequency
            // in string X is equal to or less
            // than the frequency in string Y.
            // Thus, we go to the next position
            if (ctrx[X[i] - 'A'] == 0)
            {
                continue;
            }
 
            // Here, we try to find that character,
            // which has more frequency in string Y
            // and less in string X. We try to find
            // this character in lexicographical
            // order so that we get
            // lexicographically smaller string
            int j;
            for (j = 0; j < MAX; j++)
            {
                if ((ctry[j]) > 0)
                {
                    break;
                }
            }
 
            // This portion deals with the
            // lexicographical property.
            // Now, we put a character in string X
            // when either this character has smaller
            // value than the character present there
            // right now or if this is the last position
            // for it to exchange, else we fix the
            // character already present here in
            // this position.
            if (countx[X[i] - 'A'] == ctrx[X[i] - 'A']
                || X[i] - 'A' > j)
            {
 
                countx[X[i] - 'A']--;
                ctrx[X[i] - 'A']--;
                ctry[j]--;
                X[i] = (char) ('A' + j);
            }
            else
            {
                countx[X[i] - 'A']--;
            }
        }
        System.out.println("Anagram : " + String.valueOf(X));
        System.out.println("Number of changes made : " + change / 2);
    }
 
    // Driver code
    public static void main(String[] args)
    {
        String x = "CDBABC", y = "ADCABD";
        printAnagramAndChanges(x.toCharArray(), y.toCharArray());
    }
}
 
// This code is contributed by Rajput-Ji

Python3

# Python3 program to convert string X to
# string Y which minimum number of changes.
MAX = 26
 
# Function that converts string X
# into lexicographically smallest
# anagram of string Y with minimal changes
def printAnagramAndChanges(x, y):
    x = list(x)
    y = list(y)
    countx, county = [0] * MAX, [0] * MAX
    ctrx, ctry = [0] * MAX, [0] * MAX
 
    change = 0
    l = len(x)
 
    # Counting frequency of characters
    # in each string.
    for i in range(l):
        countx[ord(x[i]) - ord('A')] += 1
        county[ord(y[i]) - ord('A')] += 1
 
    # We maintain two more counter arrays
    # ctrx[] and ctry[]
    # Ctrx[] maintains the count of extra
    # elements present in string X than
    # string Y
    # Ctry[] maintains the count of
    # characters missing from string X
    # which should be present in string Y.
    for i in range(MAX):
        if countx[i] > county[i]:
            ctrx[i] += (countx[i] - county[i])
        elif countx[i] < county[i]:
            ctry[i] += (county[i] - countx[i])
        change += abs(county[i] - countx[i])
 
    for i in range(l):
 
        # This means that we cannot edit the
        # current character as it's frequency
        # in string X is equal to or less
        # than the frequency in string Y.
        # Thus, we go to the next position
        if ctrx[ord(x[i]) - ord('A')] == 0:
            continue
 
        # Here, we try to find that character,
        # which has more frequency in string Y
        # and less in string X. We try to find
        # this character in lexicographical
        # order so that we get
        # lexicographically smaller string
        j = 0
        for j in range(MAX):
            if ctry[j] > 0:
                break
 
        # This portion deals with the
        # lexicographical property.
        # Now, we put a character in string X
        # when either this character has smaller
        # value than the character present there
        # right now or if this is the last position
        # for it to exchange, else we fix the
        # character already present here in
        # this position.
        if countx[ord(x[i]) -
                ord('A')] == ctrx[ord(x[i]) - ord('A')] or \
                                  ord(x[i]) - ord('A') > j:
            countx[ord(x[i]) - ord('A')] -= 1
            ctrx[ord(x[i]) - ord('A')] -= 1
            ctry[j] -= 1
            x[i] = chr(ord('A') + j)
        else:
            countx[ord(x[i]) - ord('A')] -= 1
 
    print("Anagram :", ''.join(x))
    print("Number of changes made :", change // 2)
 
# Driver Code
if __name__ == "__main__":
    x = "CDBABC"
    y = "ADCABD"
    printAnagramAndChanges(x, y)
 
# This code is contributed by
# sanjeev2552

C#

// C# program to convert string X to
// string Y which minimum number of changes.
using System;
 
class GFG
{
 
    static readonly int MAX = 26;
 
    // Function that converts string X
    // into lexicographically smallest
    // anagram of string Y with minimal changes
    static void printAnagramAndChanges(char[] X,
                                        char[] Y)
    {
        int []countx = new int[MAX];
        int []county = new int[MAX];
        int []ctrx = new int[MAX];
        int []ctry = new int[MAX];
 
        int change = 0;
        int l = X.Length;
 
        // Counting frequency of characters
        // in each string.
        for (int i = 0; i < l; i++)
        {
            countx[X[i] - 'A']++;
            county[Y[i] - 'A']++;
        }
 
        // We maintain two more counter arrays
        // ctrx[] and ctry[]
        // Ctrx[] maintains the count of extra
        // elements present in string X than
        // string Y
        // Ctry[] maintains the count of
        // characters missing from string X
        // which should be present in string Y.
        for (int i = 0; i < MAX; i++)
        {
            if (countx[i] > county[i])
            {
                ctrx[i] += (countx[i] - county[i]);
            }
            else if (countx[i] < county[i])
            {
                ctry[i] += (county[i] - countx[i]);
            }
            change += Math.Abs(county[i] - countx[i]);
        }
 
        for (int i = 0; i < l; i++)
        {
 
            // This means that we cannot edit the
            // current character as it's frequency
            // in string X is equal to or less
            // than the frequency in string Y.
            // Thus, we go to the next position
            if (ctrx[X[i] - 'A'] == 0)
            {
                continue;
            }
 
            // Here, we try to find that character,
            // which has more frequency in string Y
            // and less in string X. We try to find
            // this character in lexicographical
            // order so that we get
            // lexicographically smaller string
            int j;
            for (j = 0; j < MAX; j++)
            {
                if ((ctry[j]) > 0)
                {
                    break;
                }
            }
 
            // This portion deals with the
            // lexicographical property.
            // Now, we put a character in string X
            // when either this character has smaller
            // value than the character present there
            // right now or if this is the last position
            // for it to exchange, else we fix the
            // character already present here in
            // this position.
            if (countx[X[i] - 'A'] == ctrx[X[i] - 'A']
                || X[i] - 'A' > j)
            {
 
                countx[X[i] - 'A']--;
                ctrx[X[i] - 'A']--;
                ctry[j]--;
                X[i] = (char) ('A' + j);
            }
            else
            {
                countx[X[i] - 'A']--;
            }
        }
        Console.WriteLine("Anagram : " +
                        String.Join("",X));
        Console.WriteLine("Number of changes made : " +
                            change / 2);
    }
 
    // Driver code
    public static void Main(String[] args)
    {
        String x = "CDBABC", y = "ADCABD";
        printAnagramAndChanges(x.ToCharArray(),
                                y.ToCharArray());
    }
}
 
// This code is contributed by 29AjayKumar

Javascript

<script>
 
      // JavaScript program to convert string X to
      // string Y which minimum number of changes.
      const MAX = 26;
 
      // Function that converts string X
      // into lexicographically smallest
      // anagram of string Y with minimal changes
      function printAnagramAndChanges(X, Y)
      {
        var countx = new Array(MAX).fill(0);
        var county = new Array(MAX).fill(0);
        var ctrx = new Array(MAX).fill(0);
        var ctry = new Array(MAX).fill(0);
 
        var change = 0;
        var l = X.length;
 
        // Counting frequency of characters
        // in each string.
        for (var i = 0; i < l; i++) {
          countx[X[i].charCodeAt(0) - "A".charCodeAt(0)]++;
          county[Y[i].charCodeAt(0) - "A".charCodeAt(0)]++;
        }
 
        // We maintain two more counter arrays
        // ctrx[] and ctry[]
        // Ctrx[] maintains the count of extra
        // elements present in string X than
        // string Y
        // Ctry[] maintains the count of
        // characters missing from string X
        // which should be present in string Y.
        for (var i = 0; i < MAX; i++) {
          if (countx[i] > county[i]) {
            ctrx[i] += countx[i] - county[i];
          } else if (countx[i] < county[i]) {
            ctry[i] += county[i] - countx[i];
          }
          change += Math.abs(county[i] - countx[i]);
        }
 
        for (var i = 0; i < l; i++) {
          // This means that we cannot edit the
          // current character as it's frequency
          // in string X is equal to or less
          // than the frequency in string Y.
          // Thus, we go to the next position
          if (ctrx[X[i].charCodeAt(0) -
          "A".charCodeAt(0)] === 0)
          {
            continue;
          }
 
          // Here, we try to find that character,
          // which has more frequency in string Y
          // and less in string X. We try to find
          // this character in lexicographical
          // order so that we get
          // lexicographically smaller string
          var j;
          for (j = 0; j < MAX; j++) {
            if (ctry[j] > 0) {
              break;
            }
          }
 
          // This portion deals with the
          // lexicographical property.
          // Now, we put a character in string X
          // when either this character has smaller
          // value than the character present there
          // right now or if this is the last position
          // for it to exchange, else we fix the
          // character already present here in
          // this position.
          if (
            countx[X[i].charCodeAt(0) - "A".charCodeAt(0)] ===
              ctrx[X[i].charCodeAt(0) - "A".charCodeAt(0)] ||
            X[i].charCodeAt(0) - "A".charCodeAt(0) > j
          ) {
            countx[X[i].charCodeAt(0) - "A".charCodeAt(0)]--;
            ctrx[X[i].charCodeAt(0) - "A".charCodeAt(0)]--;
            ctry[j]--;
            X[i] = String.fromCharCode("A".charCodeAt(0) + j);
          } else {
            countx[X[i].charCodeAt(0) - "A".charCodeAt(0)]--;
          }
        }
        document.write("Anagram : " + X.join("") + "<br>");
        document.write("Number of changes made : " + change / 2);
      }
 
      // Driver code
      var x = "CDBABC",
          y = "ADCABD";
      printAnagramAndChanges(x.split(""), y.split(""));
       
</script>

Producción

Anagram : ADBADC
Number of changes made : 2

Complejidad de tiempo: O (N), ya que estamos usando un bucle para atravesar N veces. Donde N es la longitud de la string.
Espacio auxiliar: O(4*26), ya que estamos usando espacio extra.

Publicación traducida automáticamente

Artículo escrito por parthendo y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

C++

Java

Python3

C#

Javascript

Deja una respuesta Cancelar la respuesta