Encuentre la string de una array que se puede convertir en una string S con un número mínimo de intercambios

Dada una string S y una array de strings arr[] de longitud N y M respectivamente, la tarea es encontrar la string de la array dada a la string S intercambiando el número mínimo de caracteres. Si no se puede convertir ninguna string a S , imprima -1.

Ejemplos:

Entrada: S = «abc», arr[] = {«acb», «xyz»}
Salida: acb
Explicación: 
La string «acb» se puede convertir en «abc» intercambiando 1 par de caracteres «a cb » -> “un ac “.
La string «xyz» no se puede convertir a «abc».
 

Entrada: S = “abc”, arr[] = {“ab”, “xy”, “cb”}
Salida: -1

Enfoque: el problema se puede resolver buscando anagramas de S de la array de strings dada y luego, para cada una de esas strings, encuentre el número mínimo de intercambios de caracteres necesarios para convertir la string en S .

Siga los pasos a continuación para resolver el problema:

  • Recorra la array de strings y para cada string presente en la array, verifique si es un anagrama de S o no.
  • Si no se encuentra tal string, imprima -1 .
  • De lo contrario, encuentre la cantidad mínima de intercambios necesarios para convertir la string actual en S, iterando sobre los caracteres de la string actual , digamos S1 .
  • Almacene la posición de los caracteres en S1 en 26 listas. Para cada carácter en S1 , agregue su índice a su lista correspondiente, es decir, la lista 0 almacena todas las posiciones del carácter ‘a’ . De manera similar, la lista 1 almacena todas las posiciones de ‘b’ y así sucesivamente.
  • Después de completar el recorrido de la string S1 , itere sobre los caracteres de la string S en sentido inverso y para cada carácter, digamos S[j] , obtenga su índice respectivo de la array de listas dada, digamos temp .
  • Ahora, el movimiento óptimo es mover el carácter en el último índice en temp al índice j . Esto es óptimo porque:

 Ilustración:

Supongamos que S = “abca”, S1 = “cbaa”
A continuación se muestra la lista generada para S1:
Lista para ‘a’ = {2, 3}
Lista para ‘b’ = {1}
Lista para ‘c’ = {0}
Iterar sobre los caracteres de S , a la inversa, inicializando minMoves con 0.

  1. S = “abc a” , i = 3
    Eliminar el último índice de la lista correspondiente a ‘a’ , es decir, 3.
    Buscar en Fenwick Tree para verificar si hay algún índice a la izquierda de este índice en Fenwick Tree o no. 
    Dado que el árbol está vacío ahora, no es necesario cambiar este índice.
    Agregue el índice 3 al Árbol Fenwick
    minMoves += (i – índice) = (3 – 3). Por lo tanto, minMoves = 0
  2. S = “ab c a”, i = 2
    Quite el último índice de la lista correspondiente a ‘c’ , es decir, 0.
    Busque en Fenwick Tree para verificar si hay algún índice a la izquierda de este índice en Fenwick Tree o no.  
    Dado que el único índice en el árbol es 3 y está a la derecha de 0, no es necesario cambiar este índice.
    Agregue el índice 0 al árbol de Fenwick
    minMoves += (i – índice) = (2 – 0). Por lo tanto, minMoves = 2
  3. S = “a b ca”, i = 1
    Eliminar el último índice de la lista correspondiente a ‘b’ , es decir, 1.
    Buscar en Fenwick Tree para verificar si hay algún índice a la izquierda de este índice en Fenwick Tree o no.  
    El conteo obtenido es 1, es decir, había un carácter a la izquierda del índice 1, que ahora está hacia su derecha.
    Agregue el índice 1 al árbol de Fenwick .
    nuevo índice = 1 – leftShit = 1 – 1 = 0
    minMoves += (i – nuevo índice) = 1 – 0 = 3
  4. S = “ a bca”, i= 0 
    Eliminar el último índice de la lista correspondiente a ‘a’ , es decir, 2.
    Buscar en el árbol de Fenwick para comprobar si hay algún índice a la izquierda de este índice en el árbol de Fenwick o no.  
    La cuenta obtenida es 2, es decir, había dos caracteres a la izquierda del índice 2, que ahora está a su derecha.
    Agregue el índice 2 al árbol de Fenwick .
    nuevo índice = 2 – leftShit = 2 – 2 = 0
    minMoves+= (i-nuevo índice) = 0 – 0 = 3

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 check is two
// strings are anagrams
bool checkIsAnagram(vector<int> charCountS,
                    vector<int> charCountS1)
{
    for(int i = 0; i < 26; i++)
    {
        if (charCountS[i] != charCountS1[i])
            return false;
    }
    return true;
}
 
// Function to return the frequency of
// characters in the array of strings
vector<int> getCharCount(string S)
{
    vector<int> charCount(26, 0);
 
    for(char i:S)
        charCount[i - 'a']++;
 
    return charCount;
}
 
// Function to return the count of
// indices to the left of this index
int get(vector<int> &fenwickTree, int index)
{
    int leftShift = 0;
    leftShift += fenwickTree[index];
 
    while (index > 0)
    {
        index -= (-index) & index;
        leftShift += fenwickTree[index];
    }
    return leftShift;
}
 
// Update function of Fenwick Tree
void update(vector<int> &fenwickTree,
                   int index)
{
    while (index < fenwickTree.size())
    {
        fenwickTree[index]++;
        index += (-index) & index;
    }
}
 
// Function to get all positions of
// characters present in the string S1
vector<vector<int>> getPositions(string S)
{
     
    //@SuppressWarnings("unchecked")
    vector<vector<int>> charPositions(26);
 
    for(int i = 0; i < S.size(); i++)
        charPositions[i - 'a'].push_back(i);
 
    return charPositions;
}
 
// Function to return the minimum number
// of swaps required to convert S1 to S
int findMinMoves(string S, string S1)
{
     
    // cout<<"run\n";
    // Stores number of swaps
    int minMoves = 0;
     
    // Initialize Fenwick Tree
    vector<int> fenwickTree(S.size() + 1);
     
    // Get all positions of characters
    // present in the string S1
    vector<int> charPositions[26];
    int j = 0;
    for(char i:S1)
    {
        charPositions[i-'a'].push_back(j);
        j++;
    }
     
    // cout<<charPositions[2].size()<<endl;
     
    // Traverse the given string in reverse
    for(int i = S.size() - 1; i >= 0; i--)
    {
         
        // Get the list corresponding
        // to character S[i]
        vector<int> temp = charPositions[S[i] - 'a'];
         
        // Size of the list
        int size = temp.size() - 1;
         
        // Get and remove last
        // indices from the list
        int index = temp[size] + 1;
        charPositions[S[i] - 'a'].pop_back();
         
        //temp.pop_back();
         
        // Count of indices to
        // the left of this index
        int leftShift = get(fenwickTree, index);
         
        // Update Fenwick T ree
        update(fenwickTree, index);
         
        // Shift the index to it's left
        index -= leftShift;
         
        // Update moves
        minMoves += abs(i - index + 1);
    }
     
    // Return moves
    return minMoves;
}
 
// Function to find anagram of S
// requiring minimum number of swaps
string getBeststring(string S, vector<string> group)
{
     
    // Initialize variables
    bool isAnagram = false;
    string beststring ="";
    int minMoves = INT_MAX;
 
    // Count frequency of characters in S
    vector<int> charCountS = getCharCount(S);
 
    // Traverse the array of strings
    for(string S1 : group)
    {
         
        // Count frequency of characters in S1
        vector<int> charCountS1 = getCharCount(S1);
 
        // cout<<S1<<endl;
        // Check if S1 is anagram of S
        bool anagram = checkIsAnagram(charCountS,
                                      charCountS1);
        //cout<<anagram<<endl;
 
        // If not an anagram of S
        if (anagram == 0)
            continue;
 
        isAnagram = true;
 
        // Count swaps required
        // to convert S to S1
        int moves = findMinMoves(S, S1);
        //cout<<moves<<endl;
 
        // Count minimum number of swaps
        if (moves < minMoves)
        {
            minMoves = moves;
            beststring = S1;
        }
    }
 
    // If no anagram is found, print -1
    return (isAnagram) ? beststring : "-1";
}
 
// Driver Code
int main()
{
    // Given string
    string S = "abcdac";
 
    // Given array of strings
    vector<string> arr = { "cbdaca",
                           "abcacd",
                           "abcdef" };
 
    string beststring = getBeststring(S, arr);
 
    // Print answer
    cout << (beststring) << endl;
}
 
// This code is contributed by mohit kumar 29

Java

// Java program for the above approach
 
import java.io.*;
import java.util.*;
 
class GFG {
 
    // Function to find anagram of S
    // requiring minimum number of swaps
    static String getBestString(String S,
                                List<String> group)
    {
        // Initialize variables
        boolean isAnagram = false;
        String bestString = null;
        int minMoves = Integer.MAX_VALUE;
 
        // Count frequency of characters in S
        int[] charCountS = getCharCount(S);
 
        // Traverse the array of strings
        for (String S1 : group) {
 
            // Count frequency of characters in S1
            int[] charCountS1 = getCharCount(S1);
 
            // Check if S1 is anagram of S
            boolean anagram
                = checkIsAnagram(charCountS,
                                 charCountS1);
 
            // If not an anagram of S
            if (!anagram)
                continue;
 
            isAnagram = true;
 
            // Count swaps required
            // to convert S to S1
            int moves = findMinMoves(S, S1);
 
            // Count minimum number of swaps
            if (moves < minMoves) {
                minMoves = moves;
                bestString = S1;
            }
        }
 
        // If no anagram is found, print -1
        return (isAnagram) ? bestString : "-1";
    }
 
    // Function to return the minimum number
    // of swaps required to convert S1 to S
    static int findMinMoves(String S, String S1)
    {
 
        // Stores number of swaps
        int minMoves = 0;
 
        // Initialize Fenwick Tree
        int[] fenwickTree = new int[S.length() + 1];
 
        // Get all positions of characters
        // present in the string S1
        List<List<Integer> > charPositions
            = getPositions(S1);
 
        // Traverse the given string in reverse
        for (int i = S.length() - 1; i >= 0; i--) {
 
            // Get the list corresponding
            // to character S[i]
            List<Integer> temp
                = charPositions.get(
                    S.charAt(i) - 'a');
 
            // Size of the list
            int size = temp.size() - 1;
 
            // Get and remove last
            // indices from the list
            int index = temp.remove(size) + 1;
 
            // Count of indices to
            // the left of this index
            int leftShift = get(
                fenwickTree, index);
 
            // Update Fenwick T ree
            update(fenwickTree, index);
 
            // Shift the index to it's left
            index -= leftShift;
 
            // Update moves
            minMoves += Math.abs(i - index + 1);
        }
 
        // Return moves
        return minMoves;
    }
 
    // Function to get all positions of
    // characters present in the string S1
    static List<List<Integer> > getPositions(
        String S)
    {
        @SuppressWarnings("unchecked")
        List<List<Integer> > charPositions
            = new ArrayList();
 
        for (int i = 0; i < 26; i++)
            charPositions.add(
                new ArrayList<Integer>());
 
        for (int i = 0; i < S.length(); i++)
            charPositions.get(
                             S.charAt(i) - 'a')
                .add(i);
 
        return charPositions;
    }
 
    // Update function of Fenwick Tree
    static void update(int[] fenwickTree,
                       int index)
    {
        while (index < fenwickTree.length) {
            fenwickTree[index]++;
            index += (-index) & index;
        }
    }
 
    // Function to return the count of
    // indices to the left of this index
    static int get(int[] fenwickTree, int index)
    {
        int leftShift = 0;
        leftShift += fenwickTree[index];
 
        while (index > 0) {
            index -= (-index) & index;
            leftShift += fenwickTree[index];
        }
        return leftShift;
    }
 
    // Function to return the frequency of
    // characters in the array of strings
    static int[] getCharCount(String S)
    {
        int[] charCount = new int[26];
 
        for (int i = 0; i < S.length(); i++)
            charCount[S.charAt(i) - 'a']++;
 
        return charCount;
    }
 
    // Function to check is two
    // strings are anagrams
    static boolean checkIsAnagram(
        int[] charCountS,
        int[] charCountS1)
    {
 
        for (int i = 0; i < 26; i++) {
            if (charCountS[i] != charCountS1[i])
                return false;
        }
 
        return true;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
 
        // Given string
        String S = "abcdac";
 
        // Given array of strings
        String arr[] = { "cbdaca",
                         "abcacd",
                         "abcdef" };
 
        String bestString
            = getBestString(S, Arrays.asList(arr));
 
        // Print answer
        System.out.println(bestString);
    }
}
Producción: 

abcacd

 

Complejidad de tiempo: O(M * N * logN)
Espacio auxiliar: O(N)

Publicación traducida automáticamente

Artículo escrito por jithin 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 *