Smallest Window

Moderate
0/80
Average time to solve is 10m
profile
Contributed by
37 upvotes
Asked in companies
ArcesiumReliance Jio Infocomm LtdGoldman Sachs

Problem statement

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'.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
cn
c
kmmdnj
mj
Sample Output 1:
c
mdnj
Explanation 1:
For the first test case when S = 'cn' and X = 'c'. 
The substrings in S which contain all the characters present in X are: 'cn' and 'n'. Out of these, the smallest substring is 'c'.

For the second test case when S = 'kmmdnj' and X = 'mj'. 
The substrings in S which contain all the characters present in X are: 'kmmdnj', 'mmdnj', 'mdnj'. Out of these, the smallest substring is 'mdnj'.
Sample Input 2:
3
ilovecodingninjas
oiln
aabaac
aba
AbbaBxA
BA
Sample Output 2:
lovecodin
aab
BxA
Hint

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.

Approaches (2)
Brute Force

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.
Time Complexity

O((|S| ^ 2) * |X|) per test case.

Note: Here, |S| denotes the length of string S, and |X| denotes the length of string X.

 

In the worst case, we are generating all the possible substrings of string S. Each substring is compared with the string X to check whether it is valid or not; this requires O(|X|) operations, assuming that accessing the hashtable requires constant time operation.

Space Complexity

O(1) per test case.

 

In the worst case, extra space is required by the hash tables. In the worst case, the size of the hashtable would be equal to 26 (Number of English alphabets); hence, the space complexity remains constant.

Code Solution
(100% EXP penalty)
Smallest Window
Full screen
Console