Last Updated: 23 Aug, 2021
Minimum Window Subsequence
Hard
Asked in companies
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.
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
Approaches
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.
Similar problems