Minimum Window Substring

Find the smallest substring that contains all characters (including duplicates) of a pattern.

sliding-window two-pointers strings hash-map

Write a function `min_window_substring(s: str, t: str) -> str` that takes two strings: `s` (the source string) and `t` (the pattern). The function must return the **minimum** length substring of `s` such that it contains **all characters** of `t**, including duplicates. If no such substring exists, return an empty string `""`. If multiple minimum windows exist, return the one with the smallest starting index (the leftmost).

Implementation requirements:
- The function signature must be exactly as given.
- The substring must be a contiguous segment of `s`.
- Characters in `t` are case-sensitive (e.g., 'a' and 'A' are distinct).
- `s` and `t` consist only of printable ASCII characters (letters, digits, punctuation, spaces).
- The solution must be efficient; an O(len(s) + len(t)) sliding window approach is expected.

Do not use any external libraries beyond Python's standard library. Do not read from network or files.

Constraints

- `0 <= len(s) <= 100,000`
- `0 <= len(t) <= 100,000`
- If `t` is empty, return `""` (since an empty string contains all characters trivially).
- If `len(t) > len(s)`, return `""` unless `t` is empty.
- The returned substring must be a valid Python string.

Example

```python
# Example 1
s = "ADOBECODEBANC"
t = "ABC"
print(min_window_substring(s, t))  # Expected: "BANC"

# Example 2
s = "a"
t = "aa"
print(min_window_substring(s, t))  # Expected: ""

# Example 3
s = "a"
t = "a"
print(min_window_substring(s, t))  # Expected: "a"

# Example 4
s = "ab"
t = "A"
print(min_window_substring(s, t))  # Expected: ""
```

45 points ~35 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Use two pointers to maintain a window [left, right]. Expand right to include characters, then shrink left when the window becomes valid.

Track character frequencies in `t` and in the current window using dictionaries or counters. A window is valid when every required character appears at least as many times as in `t`.

Maintain a variable `formed` to count how many distinct characters in `t` are currently satisfied, avoiding repeated dictionary scans.

Remember to update the answer when a valid window is found, and choose the shallowest index for ties.

Edge cases: t empty, s shorter than t, characters not present at all.

Test Results

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