# A 9ms O(n) C++ solution

• 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];
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;
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.