Dadas dos strings A y B formadas por letras minúsculas, la tarea de encontrar el número mínimo de subsecuencias necesarias para formar A a partir de B . Si es imposible de formar, imprima -1.
Ejemplos:
Entrada: A = “aacbe”, B = “aceab”
Salida: 3
Explicación:
El número mínimo de subsecuencias necesarias para crear A a partir de B es “aa”, “cb” y “e”.
Entrada: A = «geeks», B = «geekofthemonth»
Salida: -1
Explicación:
No es posible crear A, ya que falta el carácter ‘s’ en B.
Para el enfoque de fuerza bruta, consulte aquí
Número mínimo de subsecuencias necesarias para convertir una string en otro
Enfoque codicioso:
- Cree una array 2D de 26 * size_of_string_B para almacenar la aparición de índices del carácter e inicialice la array con valores ‘infinitos’.
- Mantener la array 2D con índices del carácter en la string B
- Si el valor de cualquier elemento de la array 2D es infinito, actualice el valor con el siguiente valor en la misma fila.
- Inicializar la posición del puntero a 0
- Iterar la String A y para cada carácter –
- Si la posición del puntero es 0 y si esa posición en la array 2D es infinita, entonces el carácter no está presente en la string B .
- Si el valor en la array 2D no es igual a infinito, actualice el valor de la posición con el valor presente en la array 2D para esa posición del puntero, ya que los caracteres anteriores no se pueden considerar en la subsecuencia.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ implementation for minimum
// number of subsequences required
// to convert one string to another
#include <iostream>
using namespace std;
// Function to find the minimum number
// of subsequences required to convert
// one string to another
// S2 == A and S1 == B
int findMinimumSubsequences(string A,
string B){
// At least 1 subsequence is required
// Even in best case, when A is same as B
int numberOfSubsequences = 1;
// size of B
int sizeOfB = B.size();
// size of A
int sizeOfA = A.size();
int inf = 1000000;
// Create an 2D array next[][]
// of size 26 * sizeOfB to store
// the next occurrence of a character
// ('a' to 'z') as an index [0, sizeOfA - 1]
int next[26][sizeOfB];
// Array Initialization with infinite
for (int i = 0; i < 26; i++) {
for (int j = 0; j < sizeOfB; j++) {
next[i][j] = inf;
}
}
// Loop to Store the values of index
for (int i = 0; i < sizeOfB; i++) {
next[B[i] - 'a'][i] = i;
}
// If the value of next[i][j]
// is infinite then update it with
// next[i][j + 1]
for (int i = 0; i < 26; i++) {
for (int j = sizeOfB - 2; j >= 0; j--) {
if (next[i][j] == inf) {
next[i][j] = next[i][j + 1];
}
}
}
// Greedy algorithm to obtain the maximum
// possible subsequence of B to cover the
// remaining string of A using next subsequence
int pos = 0;
int i = 0;
// Loop to iterate over the string A
while (i < sizeOfA) {
// Condition to check if the character is
// not present in the string B
if (pos == 0 &&
next[A[i] - 'a'][pos] == inf) {
numberOfSubsequences = -1;
break;
}
// Condition to check if there
// is an element in B matching with
// character A[i] on or next to B[pos]
// given by next[A[i] - 'a'][pos]
else if (pos < sizeOfB &&
next[A[i] - 'a'][pos] < inf) {
int nextIndex = next[A[i] - 'a'][pos] + 1;
pos = nextIndex;
i++;
}
// Condition to check if reached at the end
// of B or no such element exists on
// or next to A[pos], thus increment number
// by one and reinitialise pos to zero
else {
numberOfSubsequences++;
pos = 0;
}
}
return numberOfSubsequences;
}
// Driver Code
int main()
{
string A = "aacbe";
string B = "aceab";
cout << findMinimumSubsequences(A, B);
return 0;
}
Java
// Java implementation for minimum
// number of subsequences required
// to convert one String to another
class GFG
{
// Function to find the minimum number
// of subsequences required to convert
// one String to another
// S2 == A and S1 == B
static int findMinimumSubsequences(String A,
String B)
{
// At least 1 subsequence is required
// Even in best case, when A is same as B
int numberOfSubsequences = 1;
// size of B
int sizeOfB = B.length();
// size of A
int sizeOfA = A.length();
int inf = 1000000;
// Create an 2D array next[][]
// of size 26 * sizeOfB to store
// the next occurrence of a character
// ('a' to 'z') as an index [0, sizeOfA - 1]
int [][]next = new int[26][sizeOfB];
// Array Initialization with infinite
for (int i = 0; i < 26; i++) {
for (int j = 0; j < sizeOfB; j++) {
next[i][j] = inf;
}
}
// Loop to Store the values of index
for (int i = 0; i < sizeOfB; i++) {
next[B.charAt(i) - 'a'][i] = i;
}
// If the value of next[i][j]
// is infinite then update it with
// next[i][j + 1]
for (int i = 0; i < 26; i++) {
for (int j = sizeOfB - 2; j >= 0; j--) {
if (next[i][j] == inf) {
next[i][j] = next[i][j + 1];
}
}
}
// Greedy algorithm to obtain the maximum
// possible subsequence of B to cover the
// remaining String of A using next subsequence
int pos = 0;
int i = 0;
// Loop to iterate over the String A
while (i < sizeOfA) {
// Condition to check if the character is
// not present in the String B
if (pos == 0 &&
next[A.charAt(i)- 'a'][pos] == inf) {
numberOfSubsequences = -1;
break;
}
// Condition to check if there
// is an element in B matching with
// character A[i] on or next to B[pos]
// given by next[A[i] - 'a'][pos]
else if (pos < sizeOfB &&
next[A.charAt(i) - 'a'][pos] < inf) {
int nextIndex = next[A.charAt(i) - 'a'][pos] + 1;
pos = nextIndex;
i++;
}
// Condition to check if reached at the end
// of B or no such element exists on
// or next to A[pos], thus increment number
// by one and reinitialise pos to zero
else {
numberOfSubsequences++;
pos = 0;
}
}
return numberOfSubsequences;
}
// Driver Code
public static void main(String[] args)
{
String A = "aacbe";
String B = "aceab";
System.out.print(findMinimumSubsequences(A, B));
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 implementation for minimum
# number of subsequences required
# to convert one to another
# Function to find the minimum number
# of subsequences required to convert
# one to another
# S2 == A and S1 == B
def findMinimumSubsequences(A, B):
# At least 1 subsequence is required
# Even in best case, when A is same as B
numberOfSubsequences = 1
# size of B
sizeOfB = len(B)
# size of A
sizeOfA = len(A)
inf = 1000000
# Create an 2D array next[][]
# of size 26 * sizeOfB to store
# the next occurrence of a character
# ('a' to 'z') as an index [0, sizeOfA - 1]
next = [[ inf for i in range(sizeOfB)] for i in range(26)]
# Loop to Store the values of index
for i in range(sizeOfB):
next[ord(B[i]) - ord('a')][i] = i
# If the value of next[i][j]
# is infinite then update it with
# next[i][j + 1]
for i in range(26):
for j in range(sizeOfB-2, -1, -1):
if (next[i][j] == inf):
next[i][j] = next[i][j + 1]
# Greedy algorithm to obtain the maximum
# possible subsequence of B to cover the
# remaining of A using next subsequence
pos = 0
i = 0
# Loop to iterate over the A
while (i < sizeOfA):
# Condition to check if the character is
# not present in the B
if (pos == 0 and
next[ord(A[i]) - ord('a')][pos] == inf):
numberOfSubsequences = -1
break
# Condition to check if there
# is an element in B matching with
# character A[i] on or next to B[pos]
# given by next[A[i] - 'a'][pos]
elif (pos < sizeOfB and
next[ord(A[i]) - ord('a')][pos] < inf) :
nextIndex = next[ord(A[i]) - ord('a')][pos] + 1
pos = nextIndex
i += 1
# Condition to check if reached at the end
# of B or no such element exists on
# or next to A[pos], thus increment number
# by one and reinitialise pos to zero
else :
numberOfSubsequences += 1
pos = 0
return numberOfSubsequences
# Driver Code
if __name__ == '__main__':
A = "aacbe"
B = "aceab"
print(findMinimumSubsequences(A, B))
# This code is contributed by mohit kumar 29
C#
// C# implementation for minimum
// number of subsequences required
// to convert one String to another
using System;
class GFG
{
// Function to find the minimum number
// of subsequences required to convert
// one String to another
// S2 == A and S1 == B
static int findMinimumSubsequences(String A,
String B)
{
// At least 1 subsequence is required
// Even in best case, when A is same as B
int numberOfSubsequences = 1;
// size of B
int sizeOfB = B.Length;
// size of A
int sizeOfA = A.Length;
int inf = 1000000;
// Create an 2D array next[,]
// of size 26 * sizeOfB to store
// the next occurrence of a character
// ('a' to 'z') as an index [0, sizeOfA - 1]
int [,]next = new int[26,sizeOfB];
// Array Initialization with infinite
for (int i = 0; i < 26; i++)
{
for (int j = 0; j < sizeOfB; j++)
{
next[i, j] = inf;
}
}
// Loop to Store the values of index
for (int i = 0; i < sizeOfB; i++)
{
next[B[i] - 'a', i] = i;
}
// If the value of next[i,j]
// is infinite then update it with
// next[i,j + 1]
for (int i = 0; i < 26; i++)
{
for (int j = sizeOfB - 2; j >= 0; j--)
{
if (next[i, j] == inf)
{
next[i, j] = next[i, j + 1];
}
}
}
// Greedy algorithm to obtain the maximum
// possible subsequence of B to cover the
// remaining String of A using next subsequence
int pos = 0;
int I = 0;
// Loop to iterate over the String A
while (I < sizeOfA)
{
// Condition to check if the character is
// not present in the String B
if (pos == 0 &&
next[A[I]- 'a', pos] == inf)
{
numberOfSubsequences = -1;
break;
}
// Condition to check if there
// is an element in B matching with
// character A[i] on or next to B[pos]
// given by next[A[i] - 'a',pos]
else if (pos < sizeOfB &&
next[A[I] - 'a',pos] < inf)
{
int nextIndex = next[A[I] - 'a',pos] + 1;
pos = nextIndex;
I++;
}
// Condition to check if reached at the end
// of B or no such element exists on
// or next to A[pos], thus increment number
// by one and reinitialise pos to zero
else
{
numberOfSubsequences++;
pos = 0;
}
}
return numberOfSubsequences;
}
// Driver Code
public static void Main(String[] args)
{
String A = "aacbe";
String B = "aceab";
Console.Write(findMinimumSubsequences(A, B));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript implementation for minimum
// number of subsequences required
// to convert one String to another
// Function to find the minimum number
// of subsequences required to convert
// one String to another
// S2 == A and S1 == B
function findMinimumSubsequences(A,B)
{
// At least 1 subsequence is required
// Even in best case, when A is same as B
let numberOfSubsequences = 1;
// size of B
let sizeOfB = B.length;
// size of A
let sizeOfA = A.length;
let inf = 1000000;
// Create an 2D array next[][]
// of size 26 * sizeOfB to store
// the next occurrence of a character
// ('a' to 'z') as an index [0, sizeOfA - 1]
let next = new Array(26);
// Array Initialization with infinite
for (let i = 0; i < 26; i++) {
next[i]=new Array(sizeOfB);
for (let j = 0; j < sizeOfB; j++) {
next[i][j] = inf;
}
}
// Loop to Store the values of index
for (let i = 0; i < sizeOfB; i++) {
next[B[i].charCodeAt(0) - 'a'.charCodeAt(0)][i] = i;
}
// If the value of next[i][j]
// is infinite then update it with
// next[i][j + 1]
for (let i = 0; i < 26; i++) {
for (let j = sizeOfB - 2; j >= 0; j--) {
if (next[i][j] == inf) {
next[i][j] = next[i][j + 1];
}
}
}
// Greedy algorithm to obtain the maximum
// possible subsequence of B to cover the
// remaining String of A using next subsequence
let pos = 0;
let i = 0;
// Loop to iterate over the String A
while (i < sizeOfA) {
// Condition to check if the character is
// not present in the String B
if (pos == 0 &&
next[A[i].charCodeAt(0)- 'a'.charCodeAt(0)][pos] == inf) {
numberOfSubsequences = -1;
break;
}
// Condition to check if there
// is an element in B matching with
// character A[i] on or next to B[pos]
// given by next[A[i] - 'a'][pos]
else if (pos < sizeOfB &&
next[A[i].charCodeAt(0) - 'a'.charCodeAt(0)][pos] < inf) {
let nextIndex = next[A[i].charCodeAt(0) - 'a'.charCodeAt(0)][pos] + 1;
pos = nextIndex;
i++;
}
// Condition to check if reached at the end
// of B or no such element exists on
// or next to A[pos], thus increment number
// by one and reinitialise pos to zero
else {
numberOfSubsequences++;
pos = 0;
}
}
return numberOfSubsequences;
}
// Driver Code
let A = "aacbe";
let B = "aceab";
document.write(findMinimumSubsequences(A, B));
// This code is contributed by unknown2108
</script>
Producción:
3
Complejidad de Tiempo: O(N), donde N es la longitud de la string a formar (aquí A)
Complejidad de Espacio Auxiliar: O(N), donde N es la longitud de la string a formar (aquí A)