Minimum Window Subsequence

Hard
0/120
Average time to solve is 27m
profile
Contributed by
102 upvotes
Asked in companies
AmazonNagarro SoftwareTummee

Problem statement

You are given two strings ‘S’ and ‘T’. Your task is to find the minimum (Contiguous) substring ‘W’ of ‘S’, such that ‘T’ is a subsequence of ‘W’

A subsequence is a sequence that can be derived from another sequence by removing zero or more elements, without changing the order.

A substring is a contiguous part of a string.

For example: 
For the given string “CodingNinjas”: “Ninja” is a substring while “dinas” is a subsequence.

If there is no such Window in ‘S’ that covers all characters in ‘T’, return an empty string "". If there are multiple such minimum length windows, return the one with the smallest starting index.

Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains a single integer ‘T’ denoting the number of test cases, then each test case follows.

The first line of each test case contains the string ‘S’.
The second line of each test case contains the string ‘T’.
Output Format : 
For each test case, print the substring of minimum length such that.

Output for each test case will be printed in a separate line.
Note : 
  You are not required to print anything; it has already been taken care of. Just implement the function.
Constraints : 
1 <= S <= 1000      
1 <= T <= 100

Time limit: 1 sec
Sample Input 1 :
2
rdew
u
abcdebdde
bde
Sample Output 1 :
""
bcde
Explanation For Sample Output 1 :
For test case 1 :
Since there is no window in ‘S’ which covers all characters of ‘T’ so therefore we returned an empty string.

For test case 2 :
“bcde” is the substring of minimum length in which we find “bde”. “bdde” is also a substring of minimum length however the index of “bcde” occurs first, therefore we returned bcde
Sample Input 2:
2
hello
eo
goodbye
dy
Sample Output 2:
ello
dby
Hint

First, at least try to find a window where the whole string ‘T’ is present. Then try to reduce the size of this window.

Approaches (1)
2-Pointers

We will find the window where we can actually find the whole string ‘T’. Then after that, since we have to return the minimum length window, we will try to shrink this window as much as possible. 

 

The steps are as follows :
 

  • Maintain 2 pointers i,j and initialize them to 0. Position of i indicates string ‘S’ and position of ‘J’ indicates ‘T’
  • Whenever S[i] == T[j], then move both the pointers ahead, otherwise move only i pointer ahead.
  • When the value of j becomes equal to T.size(), then we know that we have finally found our string ‘T’ in string ‘S’. Now it’s time to shrink this window.
  • Before shrinking let us understand why there are redundant characters that can be removed.
  • Each time we were increasing the ith pointer in the starting.
    • For example, let us consider the following strings, where S = “abcdebdde”, and T = “bde”.
    • abcdebdde              bde

                      ^(i)                        ^(j)

  • In this case, our pointers are as shown. Initially, we took the letter ‘a’ as an extra letter that can be removed. So, therefore, in order to remove these extra characters, we will again go in reverse order until j>=0. Covering the whole pattern again backwards will definitely produce the minimum window possible. We will mark the current position of i as ‘End’.
  • Now after traversing backward, our pointers will look like
    • abcdebdde              bde

                ^(i)                          ^(j)

  • When j finally reach the starting point, we realized that the whole pattern is traversed, and the length of the minimum window is end-i.
  • We will repeat this process again for the rest of our string, and update our current minimum.
Time Complexity

O( N ^ 2 ), where N is the length of string ‘S’

 

As we are first moving forward, and then backwards. At ith iteration, in the worst case, we might have to traverse the string till the end. So at each index, if we are traversing the whole string again, complexity will be O(N ^ 2)

Space Complexity

We have not used any extra space.

Video Solution
Unlock at level 3
(75% EXP penalty)
Code Solution
(100% EXP penalty)
Minimum Window Subsequence
Full screen
Console