 # LeetCode Minimum Swaps to Group All 1's Together Solution

Given two strings `s` and `t` of lengths `m` and `n` respectively, return the minimum window

substring

of `s` such that every character in `t` (including duplicates) is included in the window. If there is no such substring, return the empty string `""`.

The testcases will be generated such that the answer is unique.

Example 1:

Input: `s = "ADOBECODEBANC", t = "ABC"`
Output: `"BANC"`
Explanation: The minimum window substring "BANC" includes 'A', 'B', and 'C' from string t.

Example 2:

Input: `s = "a", t = "a"`
Output: `"a"`
Explanation: The entire string s is the minimum window.

Example 3:

Input: `s = "a", t = "aa"`
Output: `""`
Explanation: Both 'a's from t must be included in the window. Since the largest window of s only has one 'a', return empty string.

Constraints:

• `m == s.length`
• `n == t.length`
• `1 <= m, n <= 105`
• `s` and `t` consist of uppercase and lowercase English letters.

Follow up: Could you find an algorithm that runs in `O(m + n)` time?

## Solution

We will use a sliding window to find the minimum window. We wish to use a `charmap` to store the number of characters seen in `s`, and we will use two indices to represent an interval (left inclusive, right exclusive) of the `window`. To ensure that all characters in `t` is included, we can initialize `charmap` to negative counts for each character in `t`, so that when we iterate `s` and increase the counter for each `c`, we know that `charmap[c] >= 0` means that `s` contains enough `c` to satisfy the condition. So the window is valid when every value in `charmap` is non-negative, thus we can find the smallest window.

Notice that our window interval is initialized with `(-m, 0)` which has a length `m` but will produce `""` if we were to obtain `s[-m:0]`.

#### Implementation

``````1def minWindow(self, s: str, t: str) -> str:
2    m, n = len(s), len(t)
3    if m < n:
4        return ""
5    charmap = defaultdict(int)
6    for c in t:
7        charmap[c] -= 1
8    window, l = (-m, 0), 0
9
10    for r in range(m):
11        charmap[s[r]] += 1
12        r += 1
13        while min(charmap.values()) >= 0:       # valid
14            if window - window >= r - l:  # smaller than current
15                window = (l, r)
16            charmap[s[l]] -= 1
17            l += 1
18
19    return s[window : window]``````