Dadas dos strings A y B , la tarea es contar el número mínimo de operaciones necesarias para convertir la string A en B. En una operación, seleccione una subsecuencia de la string A y convierta cada carácter de esa subsecuencia al carácter más pequeño presente en ella. Si no es posible transformar, imprima “-1” .
Ejemplos:
Entrada: A = «abcab», B = «aabab»
Salida: 2
Explicación:
Operación 1: Reemplazar los caracteres de los índices {2, 1} por el carácter más pequeño de esos índices (es decir, ‘b’), transforma A en «abbab» .
Operación 2: Reemplazar los caracteres de los índices {1, 0}, por el carácter más pequeño de esos índices (es decir, ‘a’), transforma A en “aabab”.
Por lo tanto, el recuento de operaciones necesarias para convertir la string A en B es 2.Entrada: A = “aaa”, B = “aab”
Salida: -1
Explicación:
No hay forma posible de convertir A en B ya que la string A no contiene ‘b’ .
Enfoque: el enfoque se basa en la idea de que si cualquier carácter en el índice i de la string A es menor que el carácter en el índice i de la string B, entonces es imposible cambiar A a B porque cambiar un carácter a un carácter más pequeño que él mismo No se permite. A continuación se muestran los pasos:
- Inicialice dos arreglos de vectores convChar y str1array , de tamaño 26. Cada índice de estos arreglos corresponde a un carácter.
- El i -ésimo índice de convChar contiene índices de la string A que deben convertirse al i -ésimo alfabeto y str1array contiene los índices de todos los caracteres de la string A.
- Inicialice un Hashmap convertMap que indique el carácter particular al que se debe convertir el carácter en el índice i de la string A.
- Iterar sobre ambas strings simultáneamente, pueden ocurrir tres casos posibles:
- Si el i -ésimo carácter de la string A es menor que el i -ésimo carácter de la string B , entonces es imposible cambiar A por B. Por lo tanto, imprima “-1” .
- Si ambos caracteres en el índice actual son iguales, entonces no requiere ningún cambio.
- De lo contrario, inserte este índice i en la array convChar en el índice correspondiente al i -ésimo carácter de la string B e inserte el valor de carácter del i -ésimo carácter en la string B en Hashmap convertMap con el valor clave como i.
- Inicialice una variable ret que cuente las operaciones mínimas requeridas y un vector retV para almacenar el conjunto de operaciones.
- Ahora itera sobre todos los alfabetos en orden inverso. Realice los siguientes pasos en cada iteración:
- Verifique para cada alfabeto, si hay al menos un índice que deba convertirse al alfabeto actual.
- Aumente ret en uno para contar el número requerido de pasos. Sea v el vector de índices que se debe convertir al alfabeto actual con índice i y v1 el vector que contiene todos los índices de la string A . Entonces pueden darse dos casos:
- Si v1 no tiene ningún elemento , entonces el alfabeto actual no está presente en la string A. Por lo tanto, no es posible cambiar A por B.
- De lo contrario, continúe con el siguiente paso.
- Iterar para cada índice j del vector v1 . En esta iteración, busque el índice mínimo para incluir en el conjunto S .
- Si el j -ésimo alfabeto del vector v1 está presente en convertMap , significa que este alfabeto se ha convertido o se convertirá a otro carácter en una operación. Si se ha convertido en una de las operaciones anteriores, continúe con la siguiente iteración de v1 .
- De lo contrario, agregue este índice en el conjunto. Y sal del bucle
- Si no se encuentra ningún índice j en el vector v1 , entonces es imposible convertir la string A en B. Por lo tanto, imprime «-1»
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 return the minimum number // of operation void transformString(string str1, string str2) { // Storing data int N = str1.length(); vector<int> convChar[26]; vector<int> str1array[26]; // Initialize both arrays for (int i = 0; i < 26; i++) { vector<int> v; convChar[i] = v; str1array[i] = v; } // Stores the index of character map<int, char> convertMap; // Filling str1array, convChar // and hashmap convertMap. for (int i = 0; i < N; i++) { str1array[str1[i] - 'a'].push_back(i); } for (int i = 0; i < N; i++) { // Not possible to convert if (str1[i] < str2[i]) { cout << -1 << endl; return; } else if (str1[i] == str2[i]) continue; else { convChar[str2[i] - 'a'].push_back(i); convertMap[i] = str2[i]; } } // Calculate result // Initializing return values int ret = 0; vector<vector<int> > retv; // Iterating the character from // the end for (int i = 25; i >= 0; i--) { vector<int> v = convChar[i]; if (v.size() == 0) continue; // Increment the number of // operations ret++; vector<int> v1 = str1array[i]; // Not possible to convert if (v1.size() == 0) { cout << -1 << endl; return; } // to check whether the final // element has been added // in set S or not. bool isScompleted = false; for (int j = 0; j < v1.size(); j++) { // Check if v1[j] is present // in hashmap or not if (convertMap.find(v1[j]) != convertMap.end()) { char a = convertMap[v1[j]]; // Already converted then // then continue if (a > i + 'a') continue; else { v.push_back(v1[j]); isScompleted = true; retv.push_back(v); break; } } else { v.push_back(v1[j]); isScompleted = true; retv.push_back(v); break; } } // Not possible to convert if (!isScompleted) { cout << -1 << endl; return; } } // Print the result cout << ret << endl; } // Driver Code int main() { // Given strings string A = "abcab"; string B = "aabab"; // Function Call transformString(A, B); return 0; }
Java
// Java program for the above approach import java.util.*; import java.lang.*; class GFG{ // Function to return the minimum number // of operation static void transformString(String str1, String str2) { // Storing data int N = str1.length(); ArrayList< ArrayList<Integer>> convChar = new ArrayList<>(); ArrayList< ArrayList<Integer>> str1array = new ArrayList<>(); // Initialize both arrays for(int i = 0; i < 26; i++) { convChar.add(new ArrayList<>()); str1array.add(new ArrayList<>()); } // Stores the index of character Map<Integer, Character> convertMap = new HashMap<>(); // Filling str1array, convChar // and hashmap convertMap. for(int i = 0; i < N; i++) { str1array.get(str1.charAt(i) - 'a').add(i); } for(int i = 0; i < N; i++) { // Not possible to convert if (str1.charAt(i) < str2.charAt(i)) { System.out.println(-1); return; } else if (str1.charAt(i) == str2.charAt(i)) continue; else { convChar.get(str2.charAt(i) - 'a').add(i); convertMap.put(i,str2.charAt(i)); } } // Calculate result // Initializing return values int ret = 0; ArrayList< ArrayList<Integer>> retv = new ArrayList<>(); // Iterating the character from // the end for(int i = 25; i >= 0; i--) { ArrayList<Integer> v = convChar.get(i); if (v.size() == 0) continue; // Increment the number of // operations ret++; ArrayList<Integer> v1 = str1array.get(i); // Not possible to convert if (v1.size() == 0) { System.out.println(-1); return; } // To check whether the final // element has been added // in set S or not. boolean isScompleted = false; for(int j = 0; j < v1.size(); j++) { // Check if v1[j] is present // in hashmap or not if (convertMap.containsKey(v1.get(j))) { char a = convertMap.get(v1.get(j)); // Already converted then // then continue if (a > i + 'a') continue; else { v.add(v1.get(j)); isScompleted = true; retv.add(v); break; } } else { v.add(v1.get(j)); isScompleted = true; retv.add(v); break; } } // Not possible to convert if (!isScompleted) { System.out.println(-1); return; } } // Print the result System.out.println(ret); } // Driver Code public static void main (String[] args) { // Given strings String A = "abcab"; String B = "aabab"; // Function call transformString(A, B); } } // This code is contributed by offbeat
Python3
# Python3 program for the above approach # Function to return the minimum number # of operation def transformString(str1, str2): # Storing data N = len(str1) convChar = [] str1array = [] # Initialize both arrays for i in range(26): convChar.append([]) str1array.append([]) # Stores the index of character convertMap = {} # Filling str1array, convChar # and hashmap convertMap. for i in range(N): str1array[ord(str1[i]) - ord('a')].append(i) for i in range(N): # Not possible to convert if (str1[i] < str2[i]): print(-1) return elif (str1[i] == str2[i]): continue else: convChar[ord(str2[i]) - ord('a')].append(i) convertMap[i] = str2[i] # Calculate result # Initializing return values ret = 0 retv = [] # Iterating the character from # the end for i in range(25, -1, -1): v = convChar[i] if (len(v) == 0): continue # Increment the number of # operations ret += 1; v1 = str1array[i] # Not possible to convert if (len(v1) == 0): print(-1) return # To check whether the final # element has been added # in set S or not. isScompleted = False for j in range(len(v1)): # Check if v1[j] is present # in hashmap or not if (v1[j] in convertMap): a = v1[j] # Already converted then # then continue if (a > i + ord('a')): continue else: v.append(v1[j]) isScompleted = True retv.append(v) break else: v.append(v1[j]) isScompleted = True retv.append(v) break # Not possible to convert if (isScompleted == False): print(-1) return # Print the result print(ret) # Driver Code A = "abcab" B = "aabab" # Function call transformString(A, B) # This code is contributed by dadi madhav
C#
// C# program for the above approach using System; using System.Collections.Generic; class GFG{ // Function to return the minimum number // of operation static void transformString(string str1, string str2) { // Storing data int N = str1.Length; List<List<int>> convChar = new List<List<int>>(); List<List<int>> str1array = new List<List<int>>(); // Initialize both arrays for(int i = 0; i < 26; i++) { convChar.Add(new List<int>()); str1array.Add(new List<int>()); } // Stores the index of character Dictionary<int, char> convertMap = new Dictionary<int, char>(); // Filling str1array, convChar // and hashmap convertMap. for(int i = 0; i < N; i++) { str1array[str1[i] - 'a'].Add(i); } for(int i = 0; i < N; i++) { // Not possible to convert if (str1[i] < str2[i]) { Console.WriteLine(-1); return; } else if (str1[i] == str2[i]) continue; else { convChar[str2[i] - 'a'].Add(i); convertMap[i] = str2[i]; } } // Calculate result // Initializing return values int ret = 0; List<List<int>> retv = new List<List<int>>(); // Iterating the character from // the end for(int i = 25; i >= 0; i--) { List<int> v = convChar[i]; if (v.Count == 0) continue; // Increment the number of // operations ret++; List<int> v1 = str1array[i]; // Not possible to convert if (v1.Count == 0) { Console.WriteLine(-1); return; } // To check whether the final // element has been added // in set S or not. bool isScompleted = false; for(int j = 0; j < v1.Count; j++) { // Check if v1[j] is present // in hashmap or not if (convertMap.ContainsKey(v1[j])) { char a = convertMap[v1[j]]; // Already converted then // then continue if (a > i + 'a') continue; else { v.Add(v1[j]); isScompleted = true; retv.Add(v); break; } } else { v.Add(v1[j]); isScompleted = true; retv.Add(v); break; } } // Not possible to convert if (!isScompleted) { Console.WriteLine(-1); return; } } // Print the result Console.WriteLine(ret); } // Driver code static void Main() { // Given strings string A = "abcab"; string B = "aabab"; // Function call transformString(A, B); } } // This code is contributed by divyesh072019
Javascript
<script> // JavaScript program for the above approach // Function to return the minimum number // of operation function transformString(str1, str2) { // Storing data let N = str1.length let convChar = [] let str1array = [] // Initialize both arrays for(let i = 0; i < 26; i++) { convChar.push([]) str1array.push([]) } // Stores the index of character let convertMap = new Map() // Filling str1array, convChar // and hashmap convertMap. for(let i = 0; i < N; i++) { str1array[str1.charCodeAt(i) - 'a'.charCodeAt(0)].push(i) } for(let i = 0; i < N; i++) { // Not possible to convert if (str1.charCodeAt(i) < str2.charCodeAt(i)) { document.write(-1) return } else if (str1[i] == str2[i]) continue else convChar[str2.charCodeAt(i) - 'a'.charCodeAt(0)].push(i) convertMap[i] = str2[i] } // Calculate result // Initializing return values let ret = 0 let retv = [] // Iterating the character from // the end for(let i = 25; i >= 0; i--) { let v = convChar[i] if (v.length == 0) continue // Increment the number of // operations ret += 1; v1 = str1array[i] // Not possible to convert if (v1.length == 0){ document.write(-1) return } // To check whether the final // element has been added // in set S or not. isScompleted = false for(let j = 0; j < v1.length; j++) { // Check if v1[j] is present // in hashmap or not if (convertMap.has(v1[j])){ let a = v1[j] // Already converted then // then continue if (a > i + 'a'.charCodeAt(0)) continue else{ v.push(v1[j]) isScompleted = true retv.append(v) break } } else{ v.push(v1[j]) isScompleted = true retv.push(v) break } } // Not possible to convert if (isScompleted == false){ document.write(-1) return } } // Print the result document.write(ret) } // Driver Code let A = "abcab" let B = "aabab" // Function call transformString(A, B) // This code is contributed by shinjanpatra </script>
2
Complejidad temporal: O(N)
Espacio auxiliar: O(N)