Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

For example,

**S** = `"ADOBECODEBANC"`

**T** = `"ABC"`

Minimum window is `"BANC"`

.

**Note:**

If there is no such window in S that covers all characters in T, return the emtpy string `""`

.

If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.

**Solution :** leetcode needs O(n) solution, so we could not use brute force solution. So how to get the first window that contains all the characters of T? use hash table would be easy. then how do we get the next window or next next window? there is a trick here. Keep adding character that is not the same as the first character to the window until we find one that is equal to first character. delete the first character and continue deleting characters until find some character that is T.

*here is the example of how it works:*

**S** = `"ADOBECODEBANC"`

**T** = `"ABC"`

hash table [A] = 1, [B] = 1, [C] = 1

scan S, until we reach C. we get first window “ADOBEC”.now hash table become [A] = 0, [B] = 0, [C] = 0.

keep adding character to the window until we find character equal to the first character in previous window. in this example, we keep adding character until we find A. hash table [A] = 0, [B] = -1(add another B before A), [C] = 0

So window becomes “ADOBECODEBA”, delete the first A. and keep deleting until some character in hash table is larger than or equal to 0. so delete D, O. B, E(another trick here is when we add B, we change hash table [B] = -1, we can continue deleting B). hash table [A] = 0, [B] = 0, [C] = 0

now the new window “CODEBA”. add character until it equal to first character C. “CODEBANC”. hash table [A] = 0, [B] = 0, [C] = 0

delete character until its hash table is larger than or equal to 0. Delete C, O, D, E

So the final answer is “BANC”.

public string MinWindow(string s, string t)
{
var dict = new Dictionary<char, int>();
for (int i = 0; i < t.Length; i++)
{
if (dict.ContainsKey(t[i]))
{
dict[t[i]]++;
}
else
{
dict.Add(t[i], 1);
}
}
var res = string.Empty;
var len = s.Length + 1;
var start = 0;
var count = t.Length;
for (int i = 0; i < s.Length; i++)
{
if (dict.ContainsKey(s[i]))
{
if (dict[s[i]]-- > 0)
{
count--;
}
}
while (count == 0)
{
if (len > i - start + 1)
{
len = i - start + 1;
res = s.Substring(start, len);
}
if (dict.ContainsKey(s[start]))
{
if (dict[s[start]]++ >= 0)
{
count++;
}
}
start++;
}
}
return res;
}