# LeetCode 76: Minimum Window Substring

## Problem Restatement

We are given two strings:

```python
s: str
t: str
```

We need to return the shortest substring of `s` that contains every character from `t`.

Characters must be counted with duplicates.

So if:

```python
t = "AABC"
```

then a valid window must contain:

```python
A: 2
B: 1
C: 1
```

If no substring of `s` can contain all characters from `t`, return:

```python
""
```

The official problem states that `s` and `t` have lengths `m` and `n`, both up to `10^5`, and the answer is unique if it exists.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Two strings `s` and `t` |
| Output | The minimum-length substring of `s` containing all characters from `t` |
| Valid window | A contiguous substring of `s` whose character counts cover `t` |
| Failure case | Return `""` if no valid window exists |

Function shape:

```python
class Solution:
    def minWindow(self, s: str, t: str) -> str:
        ...
```

## Examples

Example 1:

```python
s = "ADOBECODEBANC"
t = "ABC"
```

We need a substring containing `A`, `B`, and `C`.

One valid substring is:

```python
"ADOBEC"
```

But it is not the shortest.

Later, we find:

```python
"BANC"
```

This contains `B`, `A`, and `C`, and no shorter valid substring exists.

So the answer is:

```python
"BANC"
```

Example 2:

```python
s = "a"
t = "a"
```

The whole string already contains the target character.

Answer:

```python
"a"
```

Example 3:

```python
s = "a"
t = "aa"
```

The target needs two `a` characters.

The string `s` only has one `a`.

Answer:

```python
""
```

## First Thought: Brute Force

A direct solution is to try every substring of `s`.

For every left index `l`, we try every right index `r`, then check whether:

```python
s[l:r + 1]
```

contains all characters from `t`.

Code shape:

```python
from collections import Counter

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        need = Counter(t)
        best = ""

        for l in range(len(s)):
            for r in range(l, len(s)):
                window = Counter(s[l:r + 1])

                valid = True
                for ch in need:
                    if window[ch] < need[ch]:
                        valid = False
                        break

                if valid:
                    candidate = s[l:r + 1]
                    if best == "" or len(candidate) < len(best):
                        best = candidate

        return best
```

This checks the right idea, but it is too slow.

## Problem With Brute Force

There are `O(m^2)` substrings of `s`.

If we rebuild a counter for each substring, checking one substring can take `O(m)` time.

That can lead to:

```python
O(m^3)
```

Even if we optimize the counting, checking all substrings is still too much for `m <= 10^5`.

We need to reuse work between neighboring substrings.

## Key Insight

The substring must be contiguous.

That points to a sliding window.

We keep a window:

```python
s[left:right + 1]
```

The window has two actions:

1. Expand `right` to include more characters.
2. Move `left` forward to shrink the window.

The important rule:

When the window is missing required characters, expand it.

When the window is valid, shrink it as much as possible while keeping it valid.

This works because once a window becomes valid, adding more characters on the right keeps it valid, but may make it longer. So we should immediately try to remove useless characters from the left.

## Counting What Is Still Missing

First, count the characters required by `t`.

```python
need = Counter(t)
```

Then maintain another counter for the current window.

```python
window = {}
```

We also maintain:

```python
formed
```

This counts how many distinct required characters currently have enough frequency in the window.

For example:

```python
t = "AABC"
```

Then:

```python
need = {
    "A": 2,
    "B": 1,
    "C": 1,
}
```

The number of distinct requirements is:

```python
required = 3
```

A window is valid when:

```python
formed == required
```

That means every required character has enough count.

## Algorithm

Create `need = Counter(t)`.

Create an empty `window` counter.

Set:

```python
required = len(need)
formed = 0
left = 0
best_len = infinity
best_left = 0
```

Then move `right` from left to right through `s`.

For each character `s[right]`:

1. Add it to `window`.
2. If this character is required and its window count just reached the needed count, increase `formed`.
3. While `formed == required`, the current window is valid.
4. Record the window if it is smaller than the best answer.
5. Remove `s[left]` from the window and move `left` forward.
6. If removing `s[left]` makes a required character insufficient, decrease `formed`.

At the end, return the best window if one was found.

## Correctness

The algorithm only records a window when `formed == required`.

That condition means every character required by `t` appears in the current window with at least the required frequency. Therefore every recorded window is valid.

Now consider the minimum valid window in the string. Let it be:

```python
s[L:R + 1]
```

When the right pointer reaches `R`, all characters from this target window are inside the current sliding window, unless the left pointer has already moved past `L`.

The left pointer only moves when the current window is valid. It stops moving once removing more characters would make the window invalid.

So when `right == R`, the algorithm shrinks the left side as far as it can while preserving validity. That process considers the shortest valid window ending at `R`.

Since the algorithm does this for every possible `right`, it considers the shortest valid window ending at every position. The global minimum among those recorded windows is therefore the minimum window substring.

## Complexity

Let:

```python
m = len(s)
n = len(t)
```

| Metric | Value | Why |
|---|---|---|
| Time | `O(m + n)` | Build counts from `t`, then each pointer moves across `s` at most once |
| Space | `O(n)` | The counters store characters needed from `t` and characters seen in the window |

Since `s` and `t` contain uppercase and lowercase English letters, the practical character set is small. Still, `O(n)` is the safe general bound.

## Implementation

```python
from collections import Counter, defaultdict

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        need = Counter(t)
        window = defaultdict(int)

        required = len(need)
        formed = 0

        left = 0
        best_len = float("inf")
        best_left = 0

        for right, ch in enumerate(s):
            window[ch] += 1

            if ch in need and window[ch] == need[ch]:
                formed += 1

            while formed == required:
                current_len = right - left + 1

                if current_len < best_len:
                    best_len = current_len
                    best_left = left

                left_ch = s[left]
                window[left_ch] -= 1

                if left_ch in need and window[left_ch] < need[left_ch]:
                    formed -= 1

                left += 1

        if best_len == float("inf"):
            return ""

        return s[best_left:best_left + best_len]
```

## Code Explanation

We count the target characters first:

```python
need = Counter(t)
```

For:

```python
t = "ABC"
```

we get:

```python
{
    "A": 1,
    "B": 1,
    "C": 1,
}
```

For:

```python
t = "AABC"
```

we get:

```python
{
    "A": 2,
    "B": 1,
    "C": 1,
}
```

Then we count the current window:

```python
window = defaultdict(int)
```

The variable `required` means how many distinct characters must be satisfied.

```python
required = len(need)
```

The variable `formed` means how many of those distinct characters are currently satisfied.

```python
formed = 0
```

When we add a character on the right:

```python
window[ch] += 1
```

we check whether this character has just reached its required count:

```python
if ch in need and window[ch] == need[ch]:
    formed += 1
```

The equality check is important.

If `need["A"] == 2`, then the second `A` makes `A` satisfied.

The third `A` should not increase `formed` again.

When all required character counts are satisfied, the window is valid:

```python
while formed == required:
```

Inside this loop, we first record the current window if it is the best so far:

```python
current_len = right - left + 1

if current_len < best_len:
    best_len = current_len
    best_left = left
```

Then we try to shrink the window from the left:

```python
left_ch = s[left]
window[left_ch] -= 1
```

If removing this character makes the count too small, the window becomes invalid:

```python
if left_ch in need and window[left_ch] < need[left_ch]:
    formed -= 1
```

Then we move the left pointer:

```python
left += 1
```

At the end, if we never found a valid window, return an empty string:

```python
if best_len == float("inf"):
    return ""
```

Otherwise, return the saved best substring:

```python
return s[best_left:best_left + best_len]
```

## Testing

```python
def run_tests():
    s = Solution()

    assert s.minWindow("ADOBECODEBANC", "ABC") == "BANC"
    assert s.minWindow("a", "a") == "a"
    assert s.minWindow("a", "aa") == ""
    assert s.minWindow("AAABBC", "AABC") == "AABBC"
    assert s.minWindow("ab", "b") == "b"
    assert s.minWindow("bba", "ab") == "ba"
    assert s.minWindow("abc", "d") == ""
    assert s.minWindow("aaaaaaaaaaaabbbbbcdd", "abcdd") == "abbbbbcdd"

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `"ADOBECODEBANC", "ABC"` | Main example |
| `"a", "a"` | Smallest valid input |
| `"a", "aa"` | Duplicate requirement cannot be satisfied |
| `"AAABBC", "AABC"` | Duplicate character requirement |
| `"ab", "b"` | Answer at the end |
| `"bba", "ab"` | Window found after skipping extra character |
| `"abc", "d"` | No valid window |
| Long repeated string | Checks shrinking after many duplicate characters |