# 76. Minimum Window Substring

## Problem Statement

<br>

Given two strings `s` and `t` of lengths `m` and `n` respectively, return *the **minimum window***&#x20;

***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**.

&#x20;

**Example 1:**

<pre><code><strong>Input: s = "ADOBECODEBANC", t = "ABC"
</strong><strong>Output: "BANC"
</strong><strong>Explanation: The minimum window substring "BANC" includes 'A', 'B', and 'C' from string t.
</strong></code></pre>

**Example 2:**

<pre><code><strong>Input: s = "a", t = "a"
</strong><strong>Output: "a"
</strong><strong>Explanation: The entire string s is the minimum window.
</strong></code></pre>

**Example 3:**

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

&#x20;

**Constraints:**

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

## Intuition

```
Approach:

Basically, we need to maintain count of the t string in a map and 
maintain the same count for the s string in another map

We move the low pointer when, the count of all alphabets in window >= count of t
Shift low pointer till the condition is unmet again,

Repeat the steps
```

### Links

<https://leetcode.com/problems/minimum-window-substring/description/>

### Video Links

<https://www.youtube.com/watch?v=jSto0O4AJbM&ab_channel=NeetCode>

### Approach 1:

```
Sliding Window
```

{% code title="C++" lineNumbers="true" %}

```cpp
class Solution {
public:
    string minWindow(string S, string T) {
        string result;
        if(S.empty() || T.empty()){
            return result;
        }
        unordered_map<char, int> map;
        unordered_map<char, int> window;
        for(int i = 0; i < T.length(); i++){
            map[T[i]]++;
        }
        int minLength = INT_MAX;
        int letterCounter = 0;
        for(int slow = 0, fast = 0; fast < S.length(); fast++){
            char c = S[fast];
            if(map.find(c) != map.end()){
                window[c]++;
                if(window[c] <= map[c]){
                    letterCounter++;
                }
            }
            if(letterCounter >= T.length()){
                while(map.find(S[slow]) == map.end() || window[S[slow]] > map[S[slow]]){
                    window[S[slow]]--;
                    slow++;
                }
                if(fast - slow + 1 < minLength){
                    minLength = fast - slow + 1;
                    result = S.substr(slow, minLength);
                }
            }
        }
        return result;
    }
};
```

{% endcode %}

### Approach 2:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 3:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 4:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Similar Problems

###