Find the smallest window in a string containing all characters of another string | PHP program to find 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 i . e . , check if any character is occurring more no . of times than its occurrence in pattern , if yes then remove it from starting and also remove the useless characters . ; update window size ; If no window found ; Return substring starting from start_index and length min_len ; Driver code
< ? php define ( " no _ of _ chars " , 256 ) ; function findSubString ( & $ str , & $ pat ) { $ len1 = strlen ( $ str ) ; $ len2 = strlen ( $ pat ) ; if ( $ len1 < $ len2 ) { echo " No ▁ such ▁ window ▁ exists " ; return " " ; } $ hash_pat = array_fill ( 0 , no_of_chars , 0 ) ; $ hash_str = array_fill ( 0 , no_of_chars , 0 ) ; for ( $ i = 0 ; $ i < $ len2 ; $ i ++ ) $ hash_pat [ ord ( $ pat [ $ i ] ) ] ++ ; $ start = 0 ; $ start_index = -1 ; $ min_len = PHP_INT_MAX ; for ( $ j = 0 ; $ j < $ len1 ; $ j ++ ) { $ hash_str [ ord ( $ str [ $ j ] ) ] ++ ; if ( $ hash_str [ ord ( $ str [ $ j ] ) ] <= $ hash_pat [ ord ( $ str [ $ j ] ) ] ) $ count ++ ; if ( $ count == $ len2 ) { while ( $ hash_str [ ord ( $ str [ $ start ] ) ] > $ hash_pat [ ord ( $ str [ $ start ] ) ] || $ hash_pat [ ord ( $ str [ $ start ] ) ] == 0 ) { if ( $ hash_str [ ord ( $ str [ $ start ] ) ] > $ hash_pat [ ord ( $ str [ $ start ] ) ] ) $ hash_str [ ord ( $ str [ $ start ] ) ] -- ; $ start ++ ; } $ len_window = $ j - $ start + 1 ; if ( $ min_len > $ len_window ) { $ min_len = $ len_window ; $ start_index = $ start ; } } } if ( $ start_index == -1 ) { echo " No ▁ such ▁ window ▁ exists " ; return " " ; } return substr ( $ str , $ start_index , $ min_len ) ; } $ str = " this ▁ is ▁ a ▁ test ▁ string " ; $ pat = " tist " ; echo " Smallest ▁ window ▁ is ▁ : ▁ STRNEWLINE " . findSubString ( $ str , $ pat ) ; ? >