# Minimum Window Substring LeetCode Solution | Easy Approach Share:

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.

substring is a contiguous sequence of characters within the string.

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?

### Minimum Window SubstringSolutions

Time:  O(∣s∣+∣t∣)
Space: O(128)=O(1)

### C++

``````class Solution {
public:
string minWindow(string s, string t) {
vector<int> count(128);
int required = t.length();
int bestLeft = -1;
int minLength = s.length() + 1;

for (const char c : t)
++count[c];

for (int l = 0, r = 0; r < s.length(); ++r) {
if (--count[s[r]] >= 0)
--required;
while (required == 0) {
if (r - l + 1 < minLength) {
bestLeft = l;
minLength = r - l + 1;
}
if (++count[s[l++]] > 0)
++required;
}
}

return bestLeft == -1 ? "" : s.substr(bestLeft, minLength);
}
};
``````

### Java

`````` class Solution {
public String minWindow(String s, String t) {
int[] count = new int;
int required = t.length();
int bestLeft = -1;
int minLength = s.length() + 1;

for (final char c : t.toCharArray())
++count[c];

for (int l = 0, r = 0; r < s.length(); ++r) {
if (--count[s.charAt(r)] >= 0)
--required;
while (required == 0) {
if (r - l + 1 < minLength) {
bestLeft = l;
minLength = r - l + 1;
}
if (++count[s.charAt(l++)] > 0)
++required;
}
}

return bestLeft == -1 ? "" : s.substring(bestLeft, bestLeft + minLength);
}
}

``````

### Python

`````` class Solution:
def minWindow(self, s: str, t: str) -> str:
count = Counter(t)
required = len(t)
bestLeft = -1
minLength = len(s) + 1

l = 0
for r, c in enumerate(s):
count[c] -= 1
if count[c] >= 0:
required -= 1
while required == 0:
if r - l + 1 < minLength:
bestLeft = l
minLength = r - l + 1
count[s[l]] += 1
if count[s[l]] > 0:
required += 1
l += 1

return '' if bestLeft == -1 else s[bestLeft: bestLeft + minLength]

``````

#### Watch Tutorial

Checkout more Solutions here