Find the shortest substring in a given string that contains all the characters of a given word or Find the Smallest window in a string containing all characters of another string
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;
}