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