Find the smallest window in a string containing all characters of another string | Function ; Answer length of ans ; starting index of ans ; creating map ; References of Window ; Traversing the window ; Calculations ; Condition matching ; Sorting ans ; Sliding I Calculation for removing I ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; string Minimum_Window ( string s , string t ) { int m [ 256 ] = { 0 } ; int ans = INT_MAX ; int start = 0 ; int count = 0 ; for ( int i = 0 ; i < t . length ( ) ; i ++ ) { if ( m [ t [ i ] ] == 0 ) count ++ ; m [ t [ i ] ] ++ ; } int i = 0 ; int j = 0 ; while ( j < s . length ( ) ) { m [ s [ j ] ] -- ; if ( m [ s [ j ] ] == 0 ) count -- ; if ( count == 0 ) { while ( count == 0 ) { if ( ans > j - i + 1 ) { ans = min ( ans , j - i + 1 ) ; start = i ; } m [ s [ i ] ] ++ ; if ( m [ s [ i ] ] > 0 ) count ++ ; i ++ ; } } j ++ ; } if ( ans != INT_MAX ) return s . substr ( start , ans ) ; else return " - 1" ; } main ( ) { string s = " ADOBECODEBANC " ; string t = " ABC " ; cout << " - - > Smallest ▁ window ▁ that ▁ contain ▁ all ▁ character ▁ : ▁ " << endl ; cout << Minimum_Window ( s , t ) ; }