# Real O(N) time without hash etc

• class Solution {
public:
string minWindow(string s, string t) {
int tcount[256], tdiff=0;
memset(tcount, 0, 256*sizeof(int));

``````    for (char c : t)
if (tcount[c]++ == 0) tdiff++;

int a=0, b=-1, minlen=INT_MAX, len=s.length();
int scount[256], sdiff=0;
memset(scount, 0, 256*sizeof(int));

string ans;
while (b < len) {
while (b+1<len && sdiff<tdiff) {
b++;
if ((scount[s[b]]++)+1==tcount[s[b]])
sdiff++;
}

if (sdiff<tdiff)
break;

while (a<=b && sdiff==tdiff) {
if (b-a+1 < minlen)
minlen=b-a+1, ans=s.substr(a, minlen);

if ((scount[s[a]]--) == tcount[s[a]] && tcount[s[a]]>0)
sdiff--;
a++;
}
}

return ans;
}
``````

};

• There are two hash map implementaitions inlined in your code: `scount + sdiff` and `tcount + tdiff`. The hash function is `h(c) = c` and you have `256` buckets. Remember that `map<int, T>` is just a generalized sparse version of `T[]`.

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