Find the smallest window in a string containing all characters of another string | Python3 program to find the smallest window containing all characters of a pattern . ; Function to find smallest window containing all characters of 'pat ; Check if string ' s ▁ length ▁ is ▁ ▁ less ▁ than ▁ pattern ' s length . If yes then no such window can exist ; Store occurrence ofs characters of pattern ; Start traversing the string count = 0 count of characters ; count occurrence of characters of string ; If string ' s ▁ char ▁ matches ▁ with ▁ ▁ pattern ' s char then increment count ; if all the characters are matched ; Try to minimize the window ; update window size ; If no window found ; Return substring starting from start_index and length min_len ; Driver code
no_of_chars = 256 NEW_LINE ' NEW_LINE def findSubString ( string , pat ) : NEW_LINE INDENT len1 = len ( string ) NEW_LINE len2 = len ( pat ) NEW_LINE if len1 < len2 : NEW_LINE INDENT print ( " No ▁ such ▁ window ▁ exists " ) NEW_LINE return " " NEW_LINE DEDENT hash_pat = [ 0 ] * no_of_chars NEW_LINE hash_str = [ 0 ] * no_of_chars NEW_LINE for i in range ( 0 , len2 ) : NEW_LINE INDENT hash_pat [ ord ( pat [ i ] ) ] += 1 NEW_LINE DEDENT start , start_index , min_len = 0 , - 1 , float ( ' inf ' ) NEW_LINE for j in range ( 0 , len1 ) : NEW_LINE INDENT hash_str [ ord ( string [ j ] ) ] += 1 NEW_LINE if ( hash_str [ ord ( string [ j ] ) ] <= hash_pat [ ord ( string [ j ] ) ] ) : NEW_LINE INDENT count += 1 NEW_LINE DEDENT if count == len2 : NEW_LINE INDENT while ( hash_str [ ord ( string [ start ] ) ] > hash_pat [ ord ( string [ start ] ) ] or hash_pat [ ord ( string [ start ] ) ] == 0 ) : NEW_LINE INDENT if ( hash_str [ ord ( string [ start ] ) ] > hash_pat [ ord ( string [ start ] ) ] ) : NEW_LINE INDENT hash_str [ ord ( string [ start ] ) ] -= 1 NEW_LINE DEDENT start += 1 NEW_LINE DEDENT len_window = j - start + 1 NEW_LINE if min_len > len_window : NEW_LINE INDENT min_len = len_window NEW_LINE start_index = start NEW_LINE DEDENT DEDENT DEDENT if start_index == - 1 : NEW_LINE INDENT print ( " No ▁ such ▁ window ▁ exists " ) NEW_LINE return " " NEW_LINE DEDENT return string [ start_index : start_index + min_len ] NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT string = " this ▁ is ▁ a ▁ test ▁ string " NEW_LINE pat = " tist " NEW_LINE print ( " Smallest ▁ window ▁ is ▁ : ▁ " ) NEW_LINE print ( findSubString ( string , pat ) ) NEW_LINE DEDENT