## Algorithm

Problem Name: 76. Minimum Window Substring

Given two strings `s` and `t` of lengths `m` and `n` respectively, return the minimum window substring (A substring is a contiguous non-empty sequence of characters within a string.) 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?

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

``````
char* minWindow(char* s, char* t) {
int n = 0, cnt = { 0 };
int head, tail, start, len = -1;
char c, *p;

if (!s || !*s || !t || !*t) return NULL;

while (c = *(t ++)) {
cnt[c] ++;
n ++;   // total number of characters in T
}

while (c = s[tail ++]) {
if (cnt[c] > 0) n --;  // decrease total number if a valid character is found
cnt[c] --;  // decrease count of current character

while (n == 0) { // all characters are found
if (len == -1 || len > tail - head) {
}
cnt[c] ++;  // increase count
if (cnt[c] > 0) {
n = 1;  // a valid character was pushed out of head, will find it back from tail
}
}
}

if (len != -1) {
p = &s[start];
p[len] = 0;
} else {
p = "";
}

return p;
}
``````
Copy The Code &

Input

cmd
s = "ADOBECODEBANC", t = "ABC"

Output

cmd
"BANC"

### #2 Code Example with C++ Programming

```Code - C++ Programming```

``````
class Solution {
public:
string minWindow(string s, string t) {
unordered_mapm;
int i = 0, j = 0, count = 0, minLen = INT_MAX;
string res = "";
for(auto x: t) m[x]++, count++;
while(j < s.size()){
if(m[s[j++]]-- > 0) count--;
if(count == 0){
while(m[s[i]] < 0) m[s[i++]]++;
int len = j - i;
if(len < minLen){
minLen = len;
res = s.substr(i, len);
}
m[s[i++]]++;
count++;
}
}
return res;
}
};
``````
Copy The Code &

Input

cmd
s = "a", t = "a"

Output

cmd
"a"

### #3 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
public String minWindow(String s1, String s2) {
String window = "";
int j = 0;
int minLength = s1.length() + 1;
for (int i = 0; i < s1.length(); i++) {
if (s1.charAt(i) == s2.charAt(j)) {
j++;
if (j == s2.length()) {
int end = i + 1;
j--;
while (j >= 0) {
if (s1.charAt(i) == s2.charAt(j)) {
j--;
}
i--;
}
j++;
i++;
if (end - i < minLength) {
minLength = end - i;
window = s1.substring(i, end);
}
}
}
}
return window;
}
}
``````
Copy The Code &

Input

cmd
s = "a", t = "aa"

Output

cmd
""

### #4 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const minWindow = function(s, t) {
const map = {}
for (const c of t) {
map[c] = (map[c] || 0) + 1
}
let counter = t.length
let start = 0
let end = 0
let minLen = Infinity
let minStart = 0
while (end < s.length) {
const eChar = s[end]
if (map[eChar] > 0) {
counter--
}
map[eChar] = (map[eChar] || 0) - 1
end++
while (counter === 0) {
if (end - start < minLen) {
minStart = start
minLen = end - start
}
const sChar = s[start]
map[sChar] = (map[sChar] || 0) + 1
if (map[sChar] > 0) {
counter++
}
start++
}
}
if (minLen !== Infinity) {
return s.substring(minStart, minStart + minLen)
}
return ''
}
``````
Copy The Code &

Input

cmd
s = "a", t = "aa"

Output

cmd
""

### #5 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def minWindow(self, s, t):
cnt_s, cnt_t, n, left, r = {}, {}, len(s), set(t), -1
for c in t:
cnt_t[c] = cnt_t.get(c, 0) + 1
L = l = 0
while left:
r += 1
if r >= n:
return ""
cnt_s[s[r]] = cnt_s.get(s[r], 0) + 1
if s[r] in cnt_t and cnt_s[s[r]] == cnt_t[s[r]]:
R = r
cnt_s[s[r]] -= 1
while l < r < n:
cnt_s[s[r]] = cnt_s.get(s[r], 0) + 1
while s[l] not in cnt_t or cnt_s[s[l]] > cnt_t[s[l]]:
cnt_s[s[l]] -= 1
l += 1
if r - l < R - L:
L, R = l, r
r += 1
return s[L: R + 1]
``````
Copy The Code &

Input

cmd
s = "ADOBECODEBANC", t = "ABC"

Output

cmd
"BANC"

### #6 Code Example with C# Programming

```Code - C# Programming```

``````
namespace LeetCode
{
public class _076_MinimumWindowSubstring
{
public string MinWindow(string s, string t)
{
if (string.IsNullOrEmpty(s) || string.IsNullOrEmpty(t) || t.Length > s.Length) { return string.Empty; }

var counts = new int;
foreach (var ch in t)
counts[ch]++;

var remaining = t.Length;
int left = 0, right = 0, minStart = 0, minLength = int.MaxValue;
while (right < s.Length)
{
if (--counts[s[right++]] >= 0) remaining--;
while (remaining == 0)
{
if (right - left < minLength)
{
minLength = right - left;
minStart = left;
}
if (++counts[s[left++]] > 0) remaining++;
}
if (minLength == t.Length)
break;
}

return minLength == int.MaxValue ? string.Empty : s.Substring(minStart, minLength);
}
}
}
``````
Copy The Code &

Input

cmd
s = "ADOBECODEBANC", t = "ABC"

Output

cmd
"BANC"