## 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;
}
```