Here is a 9 ms C++ solution, it's an O(n) solution. Let me explain later.

Let M = s.size(), N = t.size();

- First, we keep 2 pointers, i and j, which points to the end and start of the substring. i and j are initialized to 0.
- For i from 0 to N-1, first include s[i] into substring. This may cause more than enough s[i], so we will pop from the j-side. while we have more than enough s[j], we increase j by 1, else we stop it. After this, we have the shortest substring that ends at i.
- If substring between j and i is enough, then we get a solution.

We can just count each character in t and substring, then we compare each character to make sure if we get a qualified substring, but we can do it better : each time we add a char (s[i]), we check if we have enough s[i] before. If not, we count it as a **valid** number. If we get N valid number, we know that the substring is qualified. In this way we don't have to do much comparisions.

```
class Solution {
public:
string minWindow(string s, string t) {
int M = t.size();
int src[128] = {0}, target[128] = {0};
for (auto item : t) target[item]++;
int cur_len = 0, min_len = INT_MAX, valid_count = 0;
string result = "";
char ch;
int i = 0, j = 0;
for (; i < s.size(); i++) {
ch = s[i];
// add s[i]
if (src[ch] < target[ch] && target[ch]>0) valid_count++;
cur_len++;
src[ch]++;
// check if we can pop any from j
ch = s[j];
while (target[ch] == 0 || src[ch] > target[ch]) {
src[ch]--;
j++;
cur_len--;
ch = s[j];
}
if (cur_len < min_len && valid_count>=M) {
min_len = cur_len;
result = s.substr(i-cur_len+1, cur_len);
}
}
return result;
}
};
```