Smallest Window

Posted: 15 Dec, 2020
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

You are given two strings S and X containing random characters. Your task is to find the smallest substring in S which contains all the characters present in X.

Example:

Let S = “abdd” and X = “bd”.

The windows in S which contain all the characters in X are: 'abdd', 'abd', 'bdd', 'bd'. 
Out of these, the smallest substring in S which contains all the characters present in X is 'bd'. 
All the other substring have a length larger than 'bd'.
Input format:
The very first line of input contains an integer T denoting the number of test cases. 

The first line of every test case contains the string S.

The second line of every test case contains the string X.
Output format:
For each test case, print the smallest window in S which contains all the characters present in X, in a separate line.
Note:
There is always a valid window in S which contains all the characters of X.  

You do not need to print anything, it has already been taken care of. Just implement the given function.
Note:
In case of multiple answers, print only the substring that occurs first.

For example: for the string S = 'cbbbc' and X = 'bc', there are 2 possible answers i.e. 'cb' and 'bc', your code should print 'cb'.
Constraints:
1 <= T <= 10 
1 <= |S|, |X| <= 10^5

Here, |S| denotes the length of string S and |X| denotes the length of string X.
Time Limit: 1 sec
Approach 1

A simple and intuitive approach could be to generate all the possible substrings of string S and choose the smallest substring which contains all the characters present in X.

This can be done by the following approach:

  1. Firstly, store the count corresponding to each character, occurring in string X, into a hashtable.
  2. Now, the next step is to generate all the possible substrings of string S.
  3. Maintain a variable to keep track of the smallest substring, which is valid. Update it every time we find a smaller valid substring.
  4. Starting from each index in string S, generate all the possible substrings.
  5. Store the count corresponding to each character, occurring in the substring, into a new hashtable.
  6. Compare the count of each character in string X to the count of the same character in the substring. Let the character being compared be denoted by ‘ch’, then two cases arise:
    • If HashTable_X[ch] <= HashTable_SUBSTRING[ch]: The substring (window) being considered contains the character ‘ch’ and the number of occurrences of ‘ch’ in substring is greater than or equal to the number of occurrences of ‘ch’ in string X. It is a valid substring, continue iterating.
    • Otherwise, the number of occurrences of ‘ch’ in substring (window) is less than the number of occurrences of ‘ch’ in string T. Hence the substring (window) being considered cannot be valid.
  7. If the substring (window) being considered is valid, and the length of this substring is smaller than the previously stored valid substring, make the current substring as the new smallest valid substring.
  8. Repeat the process from step 5 until all the substrings of string S have been compared.
  9. Return the smallest valid substring.
Try Problem