Table of Contents

## Given two strings s and t, write a function that will find the minimum window in s which will contain all the characters of t

### Example 1

**INPUT**

S = “tutorial cup”

T = “oti”

**OUTPUT**

Minimum window is “tori”

Example 2

**INPUT**

S = “zaaskzaa”

T = “zsk”

**OUTPUT**

Minimum window is “skz”

Method 1(Brute Force)

**1.** Generate all the substrings of string S

**2.** For every substring of S, check whether the substring contains all characters of string T

**3.** Print the least length substring which conatins all characters of string T

### Method 2(Efficient)

**Time Complexity : O(n)**

## Algorithm

**1.** If the length of string S is less than string T, then print “NO such window exists”. Else,

**2.** Build a count array T_count[] of string T

ie, for example 2

count of z is 1, so T_count[‘z’] = 1

count of s is 1, so T_count[‘s’] = 1

count of k is 1, so T_count[‘k’] = 1

**3.** Traverse the string S, while traversing

** a.** count occurences of characters of string S

ie, S_count[‘z’] = 1, when we are at first character of string S

S_count[‘a’] = 1, when we are at second character of string S

** b.** If string S char matches with string T’s char, then increment the count variable

ie, for example 2

First char in string S ie, char ‘z’, there is also a char ‘z’ in string T. so increament count ie, count = 1.

** c.** If the count is same as the length of the T string, then we found the window

ie,for example 2

At char ‘k’ in string S count becomes 3( same as length of string T). Therefore we found the window ie, from starting character to present character “zaask”

** d.** After finding the window, now try to minimize it by removing extra characters from beginning of current window

ie,for example 2

After we find the second occurence of char ‘z’ in string S. ie, S_count[‘z’] changes from 1 to

**2.** Which is greater than T_count[‘z’]. It means that the window contains more number of ‘z’s than it needed so remove first ‘z’ and other useless characters from starting. ie, now window becomes “skz”

**e.** update the start and minimum length of the window ie, start changes from ‘z’ to ‘s’ and min_length changes from 5 to 3

**f.** Print the minimum length window

## C++ Program

#include<bits/stdc++.h> #define NO_OF_CHARS 256 using namespace std; // Function to find smallest window containing // all characters of T string findSubString(string S, string T) { int Slen = S.length(); int Tlen = T.length(); // check if string's length is less than T's // length. If yes then no such window can exist if (Slen < Tlen) { cout << "No such window exists"; return ""; } int S_count[NO_OF_CHARS] = {0}; int T_count[NO_OF_CHARS] = {0}; // store occurrence of characters of 't' for (int i = 0; i < Tlen; i++) T_count[T[i]]++; int start = 0, start_index = -1, min_len = INT_MAX; // start traversing the string int count = 0; // count of characters for (int i = 0; i < Slen ; i++) { // count occurrence of characters of string S_count[S[i]]++; // If s's char matches with t's char // then increment count if (T_count[S[i]] != 0 && S_count[S[i]] <= T_count[S[i]] ) count++; // if all the characters are matched if (count == Tlen) { //minimizng the current window //If the current window has a character which occured more number of times //than the character in T string, then remove starting chars while ( S_count[S[start]] > T_count[S[start]] || T_count[S[start]] == 0) { if (S_count[S[start]] > T_count[S[start]]) S_count[S[start]]--; start++; } // update window size int len_window = i - start + 1; if (min_len > len_window) { min_len = len_window; start_index = start; } } } // If no window found if (start_index == -1) { cout << "No such window exists"; return ""; } // Return substring starting from start_index // and length min_len return S.substr(start_index, min_len); } int main() { string S = "tutorial cup"; string T = "oti"; cout << "Smallest window is : "<< findSubString(S, T)<<endl; return 0; }

Try It