Minimum Window Subsequence
Understand how to solve the minimum window subsequence problem by identifying the shortest substring in which a given subsequence appears. Learn to use the sliding window pattern to efficiently track subsequences within strings and handle constraints such as character order and substring length.
We'll cover the following...
Statement
Given two strings, s1 and s2, find and return the shortest substring of s1 in which all the characters of s2 appear in the same order, but not necessarily next to each other (i.e., s2 should be a subsequence of the substring).
If no such substring exists, return an empty string "". If there are multiple shortest substrings, return the one that appears first in s1 (i.e., with the left-most starting index).
Note: A substring is a contiguous sequence of characters within a string. A subsequence is a sequence of characters that can be derived from a string by deleting some characters without changing the order of the remaining characters. For example, “edu” is a substring and “cave” is a subsequence of “educative.”
Constraints:
s1.lengths2.lengths1ands2consist of uppercase and lowercase English letters.
Examples
Understand the problem
Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:
Minimum Window Subsequence
What are valid substrings of “Educative”? Multi-select
“tive”
“ude”
“cat”
“vit”
Figure it out!
We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.
Try it yourself
Implement your solution in main.java in the following coding playground:
import java.util.*;public class Main{public static String minWindow(String s1, String s2) {// Replace this placeholder return statement with your codereturn "";}}