# Minimum Window Subsequence
## Problem Statement
Given two strings, $s_1$ and $s_2$, your task is to find the shortest contiguous substring of $s_1$ such that $s_2$ is a subsequence of this substring. If there are multiple such substrings with the minimum length, you should return the one with the smallest starting index in $s_1$.
A string $A$ is a subsequence of string $B$ if $A$ can be obtained from $B$ by deleting zero or more characters from $B$ without changing the order of the remaining characters.
If no such window exists in $s_1$ that contains $s_2$ as a subsequence, return an empty string `""`.
## Input Format
- The first line contains a string $s_1$.
- The second line contains a string $s_2$.
## Output Format
Output the minimum window substring of $s_1$ that contains $s_2$ as a subsequence, or an empty string `""` if no such window exists.
## Sample Test Cases
### Sample Input 1
```
abcdebdde
bde
```
### Sample Output 1
```
bcde
```
### Sample Input 2
```
jmeqsiwvaovvnbstl
u
```
### Sample Output 2
```
```
### Sample Input 3
```
fhhjkeejkdjjs
jkj
```
### Sample Output 3
```
jkdj
```
## Constraints
- $1 \le |s_1| \le 2 \cdot 10^4$
- $1 \le |s_2| \le 100$
- Both $s_1$ and $s_2$ consist of lowercase English letters.
- Time limit: 1 second
- Memory limit: 256 MB
## Explanation
### Sample 1
For $s_1 = \text{"abcdebdde"}$ and $s_2 = \text{"bde"}$:
- The substring $s_1[1 \dots 4] = \text{"bcde"}$ contains $s_2$ as a subsequence: $b (s_1[1]), d (s_1[3]), e (s_1[4])$. Its length is $4$.
- The substring $s_1[5 \dots 8] = \text{"bdde"}$ also contains $s_2$ as a subsequence: $b (s_1[5]), d (s_1[6]), e (s_1[8])$. Its length is $4$.
Both substrings have the minimum length $4$. According to the problem statement, we should return the one with the leftmost starting index. $s_1[1 \dots 4]$ starts at index $1$, while $s_1[5 \dots 8]$ starts at index $5$. Therefore, $\text{"bcde"}$ is the correct output.
### Sample 2
For $s_1 = \text{"jmeqsiwvaovvnbstl"}$ and $s_2 = \text{"u"}$:
The character 'u' does not appear anywhere in $s_1$. Thus, no substring of $s_1$ can contain 'u' as a subsequence. The output is an empty string.
### Sample 3
For $s_1 = \text{"fhhjkeejkdjjs"}$ and $s_2 = \text{"jkj"}$:
- One possible window is $s_1[3 \dots 7] = \text{"jkeej"}$. It contains $s_2$ ($j$ from $s_1[3]$, $k$ from $s_1[4]$, $j$ from $s_1[7]$). Its length is $5$.
- Another possible window is $s_1[7 \dots 10] = \text{"jkdj"}$. It contains $s_2$ ($j$ from $s_1[7]$, $k$ from $s_1[8]$, $j$ from $s_1[10]$). Its length is $4$.
Since $4 < 5$, the window $\text{"jkdj"}$ is shorter. No other window is shorter than $4$. Therefore, $\text{"jkdj"}$ is the correct output.
Loading problem statement...