Given two strings A and B, the task is to find the smallest substring of A having B as a subsequence. If there are multiple such substrings in A, return the substring that has the smallest starting index.
Examples :
Input : A = “abcedbaced” B = “bed”
Output : “bced”
Explanation : The substring A[2 : 5] is the shortest substring that contains the string ‘B’ as a subsequence.Input : A = “abcdbad” B = “bd”
Output : “bcd”
Explanation : Although both the substrings A[2:4] and A[5:7] have the same length, the substring which has the smallest starting index is “bcd” so it is the final answer.
Naive Approach: The simplest approach to solve the given problem is to check for string B occurring as a subsequence in every substring of A.
Among such substrings, the answer will be the one shortest in length and which has the smallest index.
Time Complexity: O(N3)
Auxiliary Space: O(1)
Efficient Approach: The above approach can also be optimized by using Dynamic Programming because the above problem has Overlapping subproblems and an Optimal substructure. The subproblems can be stored in dp[][] table memoization where dp[i][j] denotes that in the substring A(0…i) there exists a subsequence corresponding to B(0…j) which begins at index dp[i][j]. Follow the steps below to solve the problem:
- Initialize a global multidimensional array dp[100][100] with all values as -1 that stores the result of each dp state.
- Each column in the dp table represents a character in string B.
- Initialize the first column of the dp array, i.e., store the nearest occurrence of the first character of string B in every prefix of string A.
- Fill the remaining columns of the dp table. For a particular character in string B at position ‘j’, check if there exists a matching character in string A.
- If A[i] == B[j], then starting index of the required substring in the string A is equal to the starting index when the first j – 1 characters of string B are matched with the first i – 1 characters of string A.
- If A[i] != B[j], then starting index of the required substring in the string A is equal to the starting index when the first j characters of string B are matched with the first i – 1 characters of string A.
- Check if any of the values in the last column of dp table is greater than or equal to 0. For a particular index i in string A, if dp[i][b – 1] >= 0, then the required substring which has B as a subsequence is A[dp[i][b-1] : i]. Update the answer with the shortest possible substring.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Stores the dp-statesint 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 resultvoid smallestSubstringUtil(string& A, string& B){ // Initialize dp array with -1 memset(dp, -1, sizeof dp); // Function call cout << smallestSubstring(A, B) << endl;}// Driver codeint main(){ // Input strings string A = "abcedbaced"; string B = "bed"; // Function Call smallestSubstringUtil(A, B); return 0;} |
Java
// Java implementation of above approachimport 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
# python3 program for the above approach# Stores the dp-statesdp = [[-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 resultdef smallestSubstringUtil(A, B): # Initialize dp array with -1 # Function call print(smallestSubstring(A, B))# Driver codeif __name__ == "__main__": # Input strings A = "abcedbaced" B = "bed" # Function Call smallestSubstringUtil(A, B)# This code is contributed by rakeshsahni |
C#
// C# program of the above approachusing 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. |
Javascript
<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> |
Output
bced
Time Complexity: O(N2)
Auxiliary Space: O(N2)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
