Longitud de la substring más pequeña de una string dada que contiene otra string como subsecuencia | conjunto 2

Dadas dos strings A y B , la tarea es encontrar la substring más pequeña de A que tenga B como subsecuencia .

Ejemplos:

Entrada: A = «abcdefababaef», B = «abf»
Salida: 5
Explicación:
la substring más pequeña de A que tiene B como subsecuencia es abcdef.
Por lo tanto, la longitud requerida es 5.

Entrada: A = “abcdefababaef”, B = “aef”
Salida: 3

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

  • Almacene todos los índices de los caracteres de A que también están presentes en B en un Map CharacterIndex .
  • Recorra todos los caracteres de la string B .
  • Compruebe si el primer carácter de la string B está presente en la string A o no:
    1. Si se determina que es cierto, inicialice dos variables firstVar y lastVar con el índice de la primera aparición de B[0] en la string A .
    2. Después de actualizar los valores, elimine ese carácter del Map CharacterIndex .
    3. De lo contrario, no es posible ninguna substring adicional.
  • Para los caracteres restantes de B , verifique si el carácter está presente en la string A o no. Si se determina que es cierto, recorra todas las apariciones de ese carácter en la string A y si el índice de ese carácter en la string A excede lastVar , actualice lastVar con ese índice. De lo contrario, no es posible ninguna substring adicional.
  • Si B se recorre por completo, actualice la respuesta con la diferencia entre firstVar y lastVar.
  • Imprime la respuesta final minimizada.

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

C++

// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the length of
// smallest substring of a having
// string b as a subsequence
int minLength(string a, string b)
{
 
    // Stores the characters present
    // in string b
    map<char, int> Char;
    for (int i = 0; i < b.length(); i++) {
 
        Char[b[i]]++;
    }
 
    // Find index of characters of a
    // that are also present in string b
    map<char, vector<int> > CharacterIndex;
 
    for (int i = 0; i < a.length(); i++) {
 
        char x = a[i];
 
        // If character is present in string b
        if (Char.find(x) != Char.end()) {
 
            // Store the index of character
            CharacterIndex[x].push_back(i);
        }
    }
 
    int len = INT_MAX;
 
    // Flag is used to check if
    // substring is possible
    int flag;
 
    while (true) {
 
        // Assume that substring is
        // possible
        flag = 1;
 
        // Stores first and last
        // indices of the substring
        // respectively
        int firstVar, lastVar;
 
        for (int i = 0; i < b.length(); i++) {
 
            // For first character of string b
            if (i == 0) {
 
                // If the first character of
                // b is not present in a
                if (CharacterIndex.find(b[i])
                    == CharacterIndex.end()) {
 
                    flag = 0;
                    break;
                }
 
                // If the first character of b
                // is present in a
                else {
 
                    int x = *(
                        CharacterIndex[b[i]].begin());
 
                    // Remove the index from map
                    CharacterIndex[b[i]].erase(
                        CharacterIndex[b[i]].begin());
 
                    // Update indices of
                    // the substring
                    firstVar = x;
                    lastVar = x;
                }
            }
 
            // For the remaining characters of b
            else {
 
                int elementFound = 0;
                for (auto e : CharacterIndex[b[i]]) {
 
                    if (e > lastVar) {
 
                        // If index possible for
                        // current character
                        elementFound = 1;
                        lastVar = e;
                        break;
                    }
                }
                if (elementFound == 0) {
 
                    // If no index is possible
                    flag = 0;
                    break;
                }
            }
        }
 
        if (flag == 0) {
 
            // If no more substring
            // is possible
            break;
        }
 
        // Update the minimum length
        // of substring
        len = min(len,
                  abs(lastVar - firstVar) + 1);
    }
 
    // Return the result
    return len;
}
 
// Driver Code
int main()
{
 
    // Given two string
    string a = "abcdefababaef";
    string b = "abf";
 
    int len = minLength(a, b);
    if (len != INT_MAX) {
 
        cout << len << endl;
    }
    else {
 
        cout << "Impossible" << endl;
    }
}

Java

// Java program to implement
// the above approach
import java.util.ArrayList;
import java.util.HashMap;
 
class GFG{
 
// Function to find the length of
// smallest substring of a having
// string b as a subsequence
static int minLength(String a, String b)
{
     
    // Stores the characters present
    // in string b
    HashMap<Character, Integer> Char = new HashMap<>();
 
    for(int i = 0; i < b.length(); i++)
    {
        Char.put(b.charAt(i),
                 Char.getOrDefault(b.charAt(i), 0) + 1);
    }
 
    // Find index of characters of a
    // that are also present in string b
    HashMap<Character, ArrayList<Integer>>
        CharacterIndex = new HashMap<>();
 
    for(int i = 0; i < a.length(); i++)
    {
        char x = a.charAt(i);
 
        // If character is present in string b
        if (Char.containsKey(x))
        {
            if (CharacterIndex.get(x) == null)
            {
                CharacterIndex.put(
                    x, new ArrayList<Integer>());
            }
             
            // Store the index of character
            CharacterIndex.get(x).add(i);
        }
    }
 
    int len = Integer.MAX_VALUE;
 
    // Flag is used to check if
    // substring is possible
    int flag;
 
    while (true)
    {
 
        // Assume that substring is
        // possible
        flag = 1;
 
        // Stores first and last
        // indices of the substring
        // respectively
        int firstVar = 0, lastVar = 0;
 
        for(int i = 0; i < b.length(); i++)
        {
             
            // For first character of string b
            if (i == 0)
            {
 
                // If the first character of
                // b is not present in a
                if (CharacterIndex.containsKey(i))
                {
                    flag = 0;
                    break;
                }
 
                // If the first character of b
                // is present in a
                else
                {
                    int x = CharacterIndex.get(b.charAt(i)).get(0);
 
                    // Remove the index from map
                    CharacterIndex.get(b.charAt(i)).remove(
                        CharacterIndex.get(b.charAt(i)).get(0));
 
                    // Update indices of
                    // the substring
                    firstVar = x;
                    lastVar = x;
                }
            }
 
            // For the remaining characters of b
            else
            {
                int elementFound = 0;
                for(var e :
                    CharacterIndex.get(b.charAt(i)))
                {
                    if (e > lastVar)
                    {
                         
                        // If index possible for
                        // current character
                        elementFound = 1;
                        lastVar = e;
                        break;
                    }
                }
                if (elementFound == 0)
                {
                     
                    // If no index is possible
                    flag = 0;
                    break;
                }
            }
        }
 
        if (flag == 0)
        {
 
            // If no more substring
            // is possible
            break;
        }
 
        // Update the minimum length
        // of substring
        len = Math.min(
            len, Math.abs(lastVar - firstVar) + 1);
    }
 
    // Return the result
    return len;
}
 
// Driver code
public static void main(String[] args)
{
     
    // Given two string
    String a = "abcdefababaef";
    String b = "abf";
 
    int len = minLength(a, b);
    if (len != Integer.MAX_VALUE)
    {
        System.out.println(len);
    }
    else
    {
        System.out.println("Impossible");
    }
}
}
 
// This code is contributed by sk944795

Python3

# Python3 program to implement
# the above approach
import sys
 
# Function to find the length of
# smallest substring of a having
# string b as a subsequence
def minLength(a, b):
     
    # Stores the characters present
    # in string b
    Char = {}
    for i in range(len(b)):
        Char[b[i]] = Char.get(b[i], 0) + 1
 
    # Find index of characters of a
    # that are also present in string b
    CharacterIndex = {}
 
    for i in range(len(a)):
        x = a[i]
 
        # If character is present in string b
        if (x in Char):
             
            # Store the index of character
            CharacterIndex[x] = CharacterIndex.get(x, [])
            CharacterIndex[x].append(i)
 
    l = sys.maxsize
 
    # Flag is used to check if
    # substring is possible
    while(True):
         
        # Assume that substring is
        # possible
        flag = 1
 
        firstVar = 0
        lastVar = 0
         
        # Stores first and last
        # indices of the substring
        # respectively
        for i in range(len(b)):
             
            # For first character of string b
            if (i == 0):
                 
                # If the first character of
                # b is not present in a
                if (b[i] not in CharacterIndex):
                    flag = 0
                    break
 
                # If the first character of b
                # is present in a
                else:
                    x = CharacterIndex[b[i]][0]
 
                    # Remove the index from map
                    CharacterIndex[b[i]].remove(
                    CharacterIndex[b[i]][0])
 
                    # Update indices of
                    # the substring
                    firstVar = x
                    lastVar = x
 
            # For the remaining characters of b
            else:
                elementFound = 0
                for e in CharacterIndex[b[i]]:
                    if (e > lastVar):
                         
                        # If index possible for
                        # current character
                        elementFound = 1
                        lastVar = e
                        break
                     
                if (elementFound == 0):
                     
                    # If no index is possible
                    flag = 0
                    break
                 
        if (flag == 0):
             
            # If no more substring
            # is possible
            break
 
        # Update the minimum length
        # of substring
        l = min(l, abs(lastVar - firstVar) + 1)
 
    # Return the result
    return l
 
# Driver Code
if __name__ == '__main__':
     
    # Given two string
    a = "abcdefababaef"
    b = "abf"
 
    l = minLength(a, b)
    if (l != sys.maxsize):
        print(l)
    else:
        print("Impossible")
         
# This code is contributed by SURENDRA_GANGWAR
Producción: 

5

 

Complejidad Temporal: O(N 2 )
Espacio Auxiliar: O(N), ya que se ha tomado N espacio extra.

Publicación traducida automáticamente

Artículo escrito por pegasus12 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *