Minimum Window Subsequence

Find the smallest substring of s that contains t as a subsequence.

sliding-window recursion dynamic-programming string

Given two strings `s` and `t`, return the minimum contiguous substring of `s` such that `t` is a subsequence of that substring. If no such window exists, return an empty string `""`.

If there are multiple windows of the same minimal length, return the one that starts earliest in `s`.

Implement the function `min_window_subsequence(s: str, t: str) -> str`.

A subsequence is a sequence that appears in the same relative order but not necessarily contiguously. For example, "ace" is a subsequence of "abcde".

### Notes
- All characters are lowercase English letters.
- The returned substring must be a contiguous slice of `s`.

Constraints

- `1 <= len(s) <= 1000`
- `1 <= len(t) <= 100`
- `s` and `t` contain only lowercase English letters.
- Time complexity should be O(len(s) * len(t)) or better.

Example

```python
>>> min_window_subsequence("abcdebdde", "bde")
"bcde"
>>> min_window_subsequence("abczdy", "bd")
"bczd"
>>> min_window_subsequence("abc", "x")
""
```

40 points ~35 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Try to find the end of a valid window by scanning forward through t, then expand backward to find the start.

For each possible start in s, greedily match t and record the end. Keep the shortest.

You can use an O(n*m) dynamic programming approach with start indices.

A backward scan after matching all of t gives the tightest left boundary.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.