Subsecuencias mínimas de una string A que deben agregarse para obtener la string B

Dadas dos strings A y B , la tarea es contar el número mínimo de operaciones necesarias para construir la string B mediante las siguientes operaciones: 
 

• Seleccione una subsecuencia de la string A .
• Agregue la subsecuencia en la string recién formada ( inicialmente vacía ).

Imprime el conteo mínimo de operaciones requeridas. Si es imposible hacer que la nueva string sea igual a B aplicando las operaciones dadas, imprima -1 .

Ejemplos:

Entrada: A = “ abc”, B = “abac”
Salida: 2
Explicación:
Inicialmente, C = “”. 
Paso 1: seleccione la subsecuencia «ab» de la string A y agréguela a la string vacía C , es decir, C = «ab».
Paso 2: seleccione la subsecuencia «ac» de la string A y agréguela al final de la string C , es decir, C = «abac». 
Ahora, la string C es la misma que la string B.
Por lo tanto, el número de operaciones requeridas es 2.

Entrada: A = «geeksforgeeks», B = «programación»
Salida: -1

Enfoque: siga los pasos a continuación para resolver este problema:

1. Inicializa un Map para mapear los caracteres presentes en la string A con sus respectivos índices.
2. Para cada carácter de la string A , realice un seguimiento de todas sus apariciones.
3. Inicialice una variable, digamos ans , para almacenar la cantidad de operaciones requeridas. Como el número de operaciones debe ser superior a 1 , establezca ans = 1 .
4. Itere sobre los caracteres de la string B y verifique si el carácter está presente en la string A o no usando Map .
5. Por último, maximice la longitud de la subsecuencia elegida de la string A para cada operación.
6. Finalmente, imprima las operaciones mínimas requeridas.

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to count the minimum
// subsequences of a string A required
// to be appended to obtain the string B
void countminOpsToConstructAString(string A,
                                   string B)
{
    // Size of the string
    int N = A.length();
 
    int i = 0;
 
    // Maps characters to their
    // respective indices
    map<char, set<int> > mp;
 
    // Insert indices of characters
    // into the sets
    for (i = 0; i < N; i++) {
        mp[A[i]].insert(i);
    }
 
    // Stores the position of the last
    // visited index in the string A.
    // Initially set it to -1.
    int previous = -1;
 
    // Stores the required count
    int ans = 1;
 
    // Iterate over the characters of B
    for (i = 0; i < B.length(); i++) {
        char ch = B[i];
 
        // If the character in B is
        // not present in A, return -1
        if (mp[ch].size() == 0) {
            cout << -1;
            return;
        }
 
        // Fetch the next index from B[i]'s set
        auto it = mp[ch].upper_bound(previous);
 
        // If the iterator points to
        // the end of that set
        if (it == mp[ch].end()) {
 
            previous = -1;
            ans++;
            --i;
            continue;
        }
 
        // If it doesn't point to the
        // end, update  previous
        previous = *it;
    }
 
    // Print the answer
    cout << ans;
}
 
// Driver Code
int main()
{
    string A = "abc", B = "abac";
    countminOpsToConstructAString(A, B);
 
    return 0;
}

# Python3 program for the above approach
from bisect import bisect_right
 
# Function to count the minimum
# subsequences of a A required
# to be appended to obtain the B
def countminOpsToConstructAString(A, B):
   
    # Size of the string
    N = len(A)
    i = 0
 
    # Maps characters to their
    # respective indices
    mp = [[] for i in range(26)]
 
    # Insert indices of characters
    # into the sets
    for i in range(N):
        mp[ord(A[i]) - ord('a')].append(i)
 
    # Stores the position of the last
    # visited index in the A.
    # Initially set it to -1.
    previous = -1
 
    # Stores the required count
    ans, i = 1, 0
 
    # Iterate over the characters of B
    while i < len(B):
        ch = B[i]
 
        # If the character in B is
        # not present in A, return -1
        if (len(mp[ord(ch) - ord('a')]) == 0):
            print(-1)
            return
 
        # Fetch the next index from B[i]'s set
        it = bisect_right(mp[ord(ch) - ord('a')], previous)
 
        # If the iterator points to
        # the end of that set
        if (it == len(mp[ord(ch) - ord('a')])):
            previous = -1
            ans += 1
            # i -= 1
            continue
 
        # If it doesn't point to the
        # end, update  previous
        previous = mp[ord(ch) - ord('a')][it]
        i += 1
 
    # Print answer
    print (ans)
 
# Driver Code
if __name__ == '__main__':
    A, B = "abc", "abac"
    countminOpsToConstructAString(A, B)
 
    # This code is contributed by mohit kumar 29.

2

Complejidad temporal: O(N * logN)
Espacio auxiliar: O(N)