Program to Find Out the Smallest Substring Containing a Specific String in Python

Suppose we have two strings s and t. We have to find the smallest substring in s, where t is also a subsequence of the substring. If that type of substring does not exist, we will return a blank string, and if there are multiple smallest substrings, we will take the leftmost one.

So, if the input is like s = "abcbfbghfb", t = "fg", then the output will be fbg

To solve this, we will follow these steps −

• N := size of S

• dp := a new list of size N initialized with infinity

• for i in range 0 to N − 1, do

  • if S[i] is same as T[0], then

    • dp[i] := 1

• for j in range 1 to size of T − 1, do

  • last := a new map

  • dp2 := a new list of size N initialized with infinity

  • for i in range 0 to N, do

    • if S[i] is same as T[j], then

      • prev_i := return the value of T[j − 1] from last

      • if prev_i is not null, then

        • dp2[i] := dp[prev_i] + (i − prev_i)

      • last[S[i]] := i

    • dp := dp2

• m := minimum of dp

• i := return the index containing m in dp

• if m is infinity, then

  • return blank string

• return S[from index i − dp[i] + 1 to i]

Let us see the following implementation to get better understanding −

Example

 Live Demo

class Solution:    def solve(self, S, T):       INF = float("inf")       N = len(S)       dp = [INF] * N       for i in range(N):          if S[i] == T[0]:             dp[i] = 1       for j in range(1, len(T)):          last = {}          dp2 = [INF] * N          for i in range(N):             if S[i] == T[j]:                prev_i = last.get(T[j − 1], None)                if prev_i is not None:                   dp2[i] = dp[prev_i] + (i − prev_i)             last[S[i]] = i          dp = dp2       m = min(dp)       i = dp.index(m)       if m == INF:          return ""       return S[i − dp[i] + 1 : i + 1] ob = Solution() print(ob.solve("abcbfbghfb","fg"))

Input

"abcbfbghfb","fg"

Output

fbg