Minimum Window Subsequence
Minimum Window and Advanced Constraints DSA practice problem on Onlearn.
Difficulty: hard.
Topics: What is the Minimum Window Subsequence problem and how can it be solved?, Strings, String Manipulation, Subsequences, Dynamic Programming, Arrays, Time Complexity, Space Complexity, Big O Notation, Loops, string matching, sliding window, dynamic programming, time complexity analysis, two pointer technique, Subsequence Problems, Dynamic Programming (DP).
Problem Statement Given two strings S and T, find the shortest substring of S that contains T as a subsequence. If no such substring exists, return an empty string. A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements. For example, ACE is a subsequence of ABCDE. Input The input consists of two lines: The first line contains string S (1 <= len(S) <= 1000). The second line contains string T (1 <= len(T) <= 100). Both S and T consist of uppercase English letters. Output Return the shortest substring of S that contains T as a subsequence. If there are multiple such substrings with the minimum length, return the one that appears first (has the smallest starting index). Example 1 Input: Output: Explanation: A D O B E C O D E B A N C A B C is a subsequence of ADOBECODEBANC. The window ADOBECODEBANC has ABC as a subsequence. The shortest window containing ABC as a subsequence is BANC (B at index 6, A at index 10, C at index 12 in original S). Example 2 Input: Output: Explanation: a b c d e a c e is a subsequence. The shortest window that contains ace is abcde itself, starting at index 0 and ending at index 4.