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);
}
}
Producción:
abcacd
Complejidad de tiempo: O(M * N * logN)
Espacio auxiliar: O(N)