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:
- Los personajes se mueven en cada movimiento. Por lo tanto, ningún movimiento está siendo desperdiciado.
- El último índice en temp estaría más cerca de j que otros índices ya que la string se itera al revés.
- Para optimizar, se puede usar un árbol de Fenwick para determinar las posiciones modificadas de los personajes en S1 , en caso de que haya cambios.
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.
- 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- 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- 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- 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); } }
abcacd
Complejidad de tiempo: O(M * N * logN)
Espacio auxiliar: O(N)