
Minimum Window Subsequence Problem Statement
You are given two strings S
and T
. Your task is to determine the smallest contiguous substring W
of S
, such that T
is a subsequence of W
.
A subsequence is a sequence that appears in the same relative order, not necessarily contiguous. A substring is a contiguous sequence of characters within a string.
Example:
Input:
S = "CodingNinjas"
T = "dinas"
Output:
"dingNinjas"
Explanation:
"Ninja" is a substring of "CodingNinjas", while "dinas" is a subsequence.
Constraints:
1 <= |S| <= 1000
1 <= |T| <= 100
- Time limit: 1 sec
Input:
The first line contains a single integer T
denoting the number of test cases. For each test case:
The first line contains the string S
.
The second line contains the string T
.
Output:
For each test case, output the minimum length substring from S
in which T
is a subsequence.
Output for each test case should be on a new line.
Note:
You are not required to print anything; it has already been taken care of. Just implement the function as described in the problem statement.

AnswerBot
5d

Find the smallest contiguous substring of S containing T as a subsequence.
Use dynamic programming to find the minimum length substring.
Iterate through S and T to find the minimum length substring.
Keep...read more

Help your peers!
Add answer anonymously...
Top Amazon Software Developer interview questions & answers
Popular interview questions of Software Developer
Top HR questions asked in Amazon Software Developer
Stay ahead in your career. Get AmbitionBox app
Helping over 1 Crore job seekers every month in choosing their right fit company
65 L+
Reviews
4 L+
Interviews
4 Cr+
Salaries
1 Cr+
Users/Month
Contribute to help millions
Get AmbitionBox app