Encuentre la longitud de la substring más pequeña de una string dada que contiene otra string como subsecuencia

Dadas dos strings A y B , la tarea es encontrar la substring más pequeña de A que tenga B como subsecuencia . Si hay varias substrings de este tipo en A , devuelve la substring que tiene el índice inicial más pequeño. 

Ejemplos: 

Entrada: A = “abcedbaced” B = “cama”
Salida: “bced”
Explicación: La substring A[2 : 5] es la substring más corta que contiene la string ‘B’ como subsecuencia.

Entrada: A = “abcdbad” B = “bd”
Salida: “bcd”
Explicación: aunque las substrings A[2:4] y A[5:7] tienen la misma longitud, la substring que tiene el índice inicial más pequeño es «bcd», por lo que es la respuesta final. 

Enfoque ingenuo: el enfoque más simple para resolver el problema dado es verificar si la string B aparece como una subsecuencia en cada substring de A.
Entre tales substrings, la respuesta será la de menor longitud y la que tenga el índice más pequeño.  

Complejidad de Tiempo: O(N ³ ) 
Espacio Auxiliar: O(1)

Enfoque eficiente:  el enfoque anterior también se puede optimizar mediante el uso de la programación dinámica porque el problema anterior tiene subproblemas superpuestos y una subestructura óptima. Los subproblemas se pueden almacenar en la tabla de memorización dp[][] donde dp[i][j] indica que en la substring A(0…i) existe una subsecuencia correspondiente a B(0…j) que comienza en el índice dp[ yo][j] . Siga los pasos a continuación para resolver el problema:

• Inicialice una array multidimensional global dp[100][100] con todos los valores como -1 que almacena el resultado de cada estado de dp .
• Cada columna de la tabla dp representa un carácter en la string B.
• Inicialice la primera columna de la array dp , es decir, almacene la ocurrencia más cercana del primer carácter de la string B en cada prefijo de la string A.
• Llene las columnas restantes de la tabla dp . Para un carácter particular en la string B en la posición ‘j’ , verifique si existe un carácter coincidente en la string A.
  • Si A[i] == B[j] , entonces el índice inicial de la substring requerida en la string A es igual al índice inicial cuando los primeros j – 1 caracteres de la string B coinciden con los primeros i – 1 caracteres de la string un _
  • Si A[i] != B[j] , entonces el índice inicial de la substring requerida en la string A es igual al índice inicial cuando los primeros j caracteres de la string B coinciden con los primeros i – 1 caracteres de la string A .
• Verifique si alguno de los valores en la última columna de la tabla dp es mayor o igual a 0 . Para un índice particular i en la string A , si dp[i][b – 1] >= 0 , entonces la substring requerida que tiene B como subsecuencia es A[dp[i][b-1] : i] . Actualice la respuesta con la substring más corta posible.

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

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Stores the dp-states
int dp[100][100];
 
// Function to find the smallest substring in string A which
// contains string B as a subsequence.
string smallestSubstring(string& A, string& B)
{
    // Size of string A
    int a = A.size();
 
    // Size of string B
    int b = B.size();
 
    // Initializing the first column of dp array.
    // Storing the occurrence of first character of string B
    // in first (i + 1) characters of string A.
    for (int i = 0; i < a; ++i) {
 
        // If the current character of string A does not
        // match the first character of string B.
        if (i > 0 and A[i] != B[0]) {
            dp[i][0] = dp[i - 1][0];
        }
 
        // If the current character of string A is equal to
        // the first character of string B.
        if (A[i] == B[0]) {
            dp[i][0] = i;
        }
    }
 
    // Iterating through remaining characters of string B.
    for (int j = 1; j < b; ++j) {
 
        // Checking if any character in string A matches
        // with the current character of string B.
        for (int i = 1; i < a; ++i) {
 
            // If there is a match, then starting index of
            // required substring in string 'A' is equal to
            // the starting index when first 'j - 1'
            // characters of string 'B' matched with first
            // 'i - 1' characters of string 'A'.
            if (A[i] == B[j]) {
                dp[i][j] = dp[i - 1][j - 1];
            }
 
            // Else, starting index of required substring in
            // string 'A' is equal to the starting index
            // when first 'j' characters of string 'B'
            // matched with first 'i - 1' characters of
            // string 'A'.
            else {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }
 
    // String for storing final answer
    string answer = "";
 
    // Length of smallest substring
    int best_length = 1e9;
 
    for (int i = 0; i < a; ++i) {
 
        // dp[i][b-1] is the index in string 'A', such that
        // the substring A(dp[i][b-1] : i) contains string
        // 'B' as a subsequence.
        if (dp[i][b - 1] != -1) {
 
            // Starting index of substring
            int start = dp[i][b - 1];
 
            // Ending index of substring
            int end = i;
 
            // Length of substring
            int current_length = end - start + 1;
 
            // if current length is lesser than the best
            // length update the answer.
            if (current_length < best_length) {
                best_length = current_length;
 
                // Update the answer
                answer = A.substr(start, best_length);
            }
        }
    }
 
    // Return the smallest substring
    return answer;
}
 
// This function is initializing dp with -1
// and printing the result
void smallestSubstringUtil(string& A, string& B)
{
    // Initialize dp array with -1
    memset(dp, -1, sizeof dp);
 
    // Function call
    cout << smallestSubstring(A, B) << endl;
}
 
// Driver code
int main()
{
    // Input strings
    string A = "abcedbaced";
    string B = "bed";
 
    // Function Call
    smallestSubstringUtil(A, B);
 
    return 0;
}

// Java implementation of above approach
import java.io.*;
import java.util.*;
 
class GFG {
 
  // Stores the dp-states
  static int[][] dp = new int[100][100];
 
  // Function to find the smallest subString in String A which
  // contains String B as a subsequence.
  static String smallestSubstring(String A, String B)
  {
     
    // Size of String A
    int a = A.length();
 
    // Size of String B
    int b = B.length();
 
    // Initializing the first column of dp array.
    // Storing the occurrence of first character of String B
    // in first (i + 1) characters of String A.
    for (int i = 0; i < a; ++i) {
 
      // If the current character of String A does not
      // match the first character of String B.
      if (i > 0 && A.charAt(i) != B.charAt(0)) {
        dp[i][0] = dp[i - 1][0];
      }
 
      // If the current character of String A is equal to
      // the first character of String B.
      if (A.charAt(i) == B.charAt(0)) {
        dp[i][0] = i;
      }
    }
 
    // Iterating through remaining characters of String B.
    for (int j = 1; j < b; ++j) {
 
      // Checking if any character in String A matches
      // with the current character of String B.
      for (int i = 1; i < a; ++i) {
 
        // If there is a match, then starting index of
        // required subString in String 'A' is equal to
        // the starting index when first 'j - 1'
        // characters of String 'B' matched with first
        // 'i - 1' characters of String 'A'.
        if (A.charAt(i) == B.charAt(j)) {
          dp[i][j] = dp[i - 1][j - 1];
        }
 
        // Else, starting index of required subString in
        // String 'A' is equal to the starting index
        // when first 'j' characters of String 'B'
        // matched with first 'i - 1' characters of
        // String 'A'.
        else {
          dp[i][j] = dp[i - 1][j];
        }
      }
    }
 
    // String for storing final answer
    String answer = "";
 
    // Length of smallest substring
    int best_length = 100000000;
 
    for (int i = 0; i < a; ++i) {
 
      // dp[i][b-1] is the index in String 'A', such that
      // the subString A(dp[i][b-1] : i) contains string
      // 'B' as a subsequence.
      if (dp[i][b - 1] != -1) {
 
        // Starting index of substring
        int start = dp[i][b - 1];
 
        // Ending index of substring
        int end = i;
 
        // Length of substring
        int current_length = end - start + 1;
 
        // if current length is lesser than the best
        // length update the answer.
        if (current_length < best_length) {
          best_length = current_length;
 
          // Update the answer
          answer = A.substring(start, best_length+1);
        }
      }
    }
 
    // Return the smallest substring
    return answer;
  }
 
  // This function is initializing dp with -1
  // and printing the result
  static void smallestSubstringUtil(String A, String B)
  {
    // Initialize dp array with -1
    for(int i=0;i<100;i++)
    {
      for(int j=0;j<100;j++)
      {
        dp[i][j] = -1;
      }
    }
 
    // Function call
    System.out.print( smallestSubstring(A, B) );
  }
 
  // Driver Code
  public static void main(String[] args)
  {
    // Input strings
    String A = "abcedbaced";
    String B = "bed";
 
    // Function Call
    smallestSubstringUtil(A, B);
  }
}
 
// This code is contributed by sanjoy_62.

# python3 program for the above approach
 
# Stores the dp-states
dp = [[-1 for _ in range(100)] for _ in range(100)]
 
# Function to find the smallest substring in string A which
# contains string B as a subsequence.
def smallestSubstring(A, B):
 
    # Size of string A
    a = len(A)
 
    # Size of string B
    b = len(B)
 
    # Initializing the first column of dp array.
    # Storing the occurrence of first character of string B
    # in first (i + 1) characters of string A.
    for i in range(0, a):
 
        # If the current character of string A does not
        # match the first character of string B.
        if (i > 0 and A[i] != B[0]):
            dp[i][0] = dp[i - 1][0]
 
        # If the current character of string A is equal to
        # the first character of string B.
        if (A[i] == B[0]):
            dp[i][0] = i
 
    # Iterating through remaining characters of string B.
    for j in range(1, b):
 
        # Checking if any character in string A matches
        # with the current character of string B.
        for i in range(1, a):
 
            # If there is a match, then starting index of
            # required substring in string 'A' is equal to
            # the starting index when first 'j - 1'
            # characters of string 'B' matched with first
            # 'i - 1' characters of string 'A'.
            if (A[i] == B[j]):
                dp[i][j] = dp[i - 1][j - 1]
 
            # Else, starting index of required substring in
            # string 'A' is equal to the starting index
            # when first 'j' characters of string 'B'
            # matched with first 'i - 1' characters of
            # string 'A'.
            else:
                dp[i][j] = dp[i - 1][j]
 
    # String for storing final answer
    answer = ""
 
    # Length of smallest substring
    best_length = 1e9
 
    for i in range(0, a):
 
        # dp[i][b-1] is the index in string 'A', such that
        # the substring A(dp[i][b-1] : i) contains string
        # 'B' as a subsequence.
        if (dp[i][b - 1] != -1):
 
            # Starting index of substring
            start = dp[i][b - 1]
 
            # Ending index of substring
            end = i
 
            # Length of substring
            current_length = end - start + 1
 
            # if current length is lesser than the best
            # length update the answer.
            if (current_length < best_length):
                best_length = current_length
 
                # Update the answer
                answer = A[start: start + best_length]
 
    # Return the smallest substring
    return answer
 
# This function is initializing dp with -1
# and printing the result
def smallestSubstringUtil(A, B):
 
    # Initialize dp array with -1
 
    # Function call
    print(smallestSubstring(A, B))
 
# Driver code
if __name__ == "__main__":
 
    # Input strings
    A = "abcedbaced"
    B = "bed"
 
    # Function Call
    smallestSubstringUtil(A, B)
 
# This code is contributed by rakeshsahni

// C# program of the above approach
using System;
using System.Linq;
using System.Collections.Generic;
 
class GFG
{
 
  // Stores the dp-states
  static int[,] dp = new int[100, 100];
 
  // Function to find the smallest substring in string A which
  // contains string B as a subsequence.
  static string smallestSubstring(string A, string B)
  {
    // Size of string A
    int a = A.Length;
 
    // Size of string B
    int b = B.Length;
 
    // Initializing the first column of dp array.
    // Storing the occurrence of first character of string B
    // in first (i + 1) characters of string A.
    for (int i = 0; i < a; ++i) {
 
      // If the current character of string A does not
      // match the first character of string B.
      if (i > 0 && A[i] != B[0]) {
        dp[i,0] = dp[i - 1, 0];
      }
 
      // If the current character of string A is equal to
      // the first character of string B.
      if (A[i] == B[0]) {
        dp[i,0] = i;
      }
    }
 
    // Iterating through remaining characters of string B.
    for (int j = 1; j < b; ++j) {
 
      // Checking if any character in string A matches
      // with the current character of string B.
      for (int i = 1; i < a; ++i) {
 
        // If there is a match, then starting index of
        // required substring in string 'A' is equal to
        // the starting index when first 'j - 1'
        // characters of string 'B' matched with first
        // 'i - 1' characters of string 'A'.
        if (A[i] == B[j]) {
          dp[i,j] = dp[i - 1,j - 1];
        }
 
        // Else, starting index of required substring in
        // string 'A' is equal to the starting index
        // when first 'j' characters of string 'B'
        // matched with first 'i - 1' characters of
        // string 'A'.
        else {
          dp[i,j] = dp[i - 1,j];
        }
      }
    }
 
    // String for storing final answer
    string answer = "";
 
    // Length of smallest substring
    int best_length = 100000000;
 
    for (int i = 0; i < a; ++i) {
 
      // dp[i][b-1] is the index in string 'A', such that
      // the substring A(dp[i][b-1] : i) contains string
      // 'B' as a subsequence.
      if (dp[i,b - 1] != -1) {
 
        // Starting index of substring
        int start = dp[i,b - 1];
 
        // Ending index of substring
        int end = i;
 
        // Length of substring
        int current_length = end - start + 1;
 
        // if current length is lesser than the best
        // length update the answer.
        if (current_length < best_length) {
          best_length = current_length;
 
          // Update the answer
          answer = A.Substring(start, best_length);
        }
      }
    }
 
    // Return the smallest substring
    return answer;
  }
 
  // This function is initializing dp with -1
  // and printing the result
  static void smallestSubstringUtil(string A, string B)
  {
    // Initialize dp array with -1
    for(int i=0;i<100;i++)
    {
      for(int j=0;j<100;j++)
      {
        dp[i,j] = -1;
      }
    }
 
    // Function call
    Console.Write( smallestSubstring(A, B));
  }
 
  // Driver Code
  public static void Main()
  {
    // Input strings
    string A = "abcedbaced";
    string B = "bed";
 
    // Function Call
    smallestSubstringUtil(A, B);
  }
}
 
// This code is contributed by sanjoy_62.

<script>
        // JavaScript code for the above approach
 
        // Stores the dp-states
        let dp = new Array(100);
        for (let i = 0; i < dp.length; i++) {
            dp[i] = new Array(100).fill(-1)
        }
 
        // Function to find the smallest substring in string A which
        // contains string B as a subsequence.
        function smallestSubstring(A, B) {
            // Size of string A
            let a = A.length;
 
            // Size of string B
            let b = B.length;
 
            // Initializing the first column of dp array.
            // Storing the occurrence of first character of string B
            // in first (i + 1) characters of string A.
            for (let i = 0; i < a; ++i) {
 
                // If the current character of string A does not
                // match the first character of string B.
                if (i > 0 && A[i] != B[0]) {
                    dp[i][0] = dp[i - 1][0];
                }
 
                // If the current character of string A is equal to
                // the first character of string B.
                if (A[i] == B[0]) {
                    dp[i][0] = i;
                }
            }
 
            // Iterating through remaining characters of string B.
            for (let j = 1; j < b; ++j) {
 
                // Checking if any character in string A matches
                // with the current character of string B.
                for (let i = 1; i < a; ++i) {
 
                    // If there is a match, then starting index of
                    // required substring in string 'A' is equal to
                    // the starting index when first 'j - 1'
                    // characters of string 'B' matched with first
                    // 'i - 1' characters of string 'A'.
                    if (A[i] == B[j]) {
                        dp[i][j] = dp[i - 1][j - 1];
                    }
 
                    // Else, starting index of required substring in
                    // string 'A' is equal to the starting index
                    // when first 'j' characters of string 'B'
                    // matched with first 'i - 1' characters of
                    // string 'A'.
                    else {
                        dp[i][j] = dp[i - 1][j];
                    }
                }
            }
 
            // String for storing final answer
            let answer = "";
 
            // Length of smallest substring
            let best_length = 1e9;
 
            for (let i = 0; i < a; ++i) {
 
                // dp[i][b-1] is the index in string 'A', such that
                // the substring A(dp[i][b-1] : i) contains string
                // 'B' as a subsequence.
                if (dp[i][b - 1] != -1) {
 
                    // Starting index of substring
                    let start = dp[i][b - 1];
 
                    // Ending index of substring
                    let end = i;
 
                    // Length of substring
                    let current_length = end - start + 1;
 
                    // if current length is lesser than the best
                    // length update the answer.
                    if (current_length < best_length) {
                        best_length = current_length;
 
                        // Update the answer
                        answer = A.slice(start, start + best_length);
                    }
                }
            }
 
            // Return the smallest substring
            return answer;
        }
 
        // This function is initializing dp with -1
        // and printing the result
        function smallestSubstringUtil(A, B) {
 
            // Function call
            document.write(smallestSubstring(A, B) + "<br>");
        }
 
        // Driver code
 
        // Input strings
        let A = "abcedbaced";
        let B = "bed";
 
        // Function Call
        smallestSubstringUtil(A, B);
 
       // This code is contributed by Potta Lokesh
    </script>

bced

Tiempo Complejidad: O(N ² ) 
Espacio Auxiliar:   O(N ² )