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>
Producción:
2
Complejidad temporal: O(N)
Espacio auxiliar: O(N)