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...
Amazon Software Developer Interview Questions
Stay ahead in your career. Get AmbitionBox app
qr-code
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

Made with ❤️ in India. Trademarks belong to their respective owners. All rights reserved © 2024 Info Edge (India) Ltd.

Follow us
  • Youtube
  • Instagram
  • LinkedIn
  • Facebook
  • Twitter