# Binary search and two pointers

LeetCode 76 Minimum Window Substring

`Runtime: 292 ms, faster than 6.73% of C++ online submissions for Minimum Window Substring.Memory Usage: 379.2 MB, less than 5.01% of C++ online submissions for Minimum Window Substring.`
`class Solution {public:    string minWindow(string s, string t) {        int low = t.length(), high =s.length();        const int n = s.length();        const int M = 256;        int min_ = 128, max_ = -1;        vector<vector<int>> cnt(n+1, vector<int>(M, 0));        for (int i =0; i < n; ++i)        {            min_ = min(int(s[i]), min_);            max_ = max(int(s[i]), max_);            cnt[i+1] = cnt[i];            cnt[i+1][s[i]] += 1;        }        vector<int> cnt_t(M, 0);               for (auto c : t)         {            min_ = min(int(c), min_);            max_ = max(int(c), max_);            cnt_t[c] += 1;                }        function<string(int)> good = [=](int k)        {            string ret = "";            for (int i = k-1; i < n; ++i)            {                bool good = true;                // if from 0 to 127 will get TLE.                for (int j =min_ ; j <= max_; ++j)                    if (cnt[i+1][j] - cnt[i-k+1][j] < cnt_t[j])                    {                        good = false;break;                    }                if (good)return s.substr(i -k+1, k);            }            return ret;        };                while (low <high)        {            int mid = low + (high - low)/2;            if (good(mid)!="")            {                high = mid;            }            else            {                low = mid + 1;            }        }        return good(low);             }};`

# O(n) solution [1]

`Runtime: 12 ms, faster than 98.83% of C++ online submissions for Minimum Window Substring.Memory Usage: 7.6 MB, less than 88.85% of C++ online submissions for Minimum Window Substring.`

For this code, we count down to indicate whether we have collected enough elements within the window of [i, j].

For example

if s = “aaab”

and t is ‘aab’

then we need 2 a and 1 b.

we traverse from left to right of the s

`i = 0, j = 0 :  we get 1 'a', we still need 1 a and 1b, we use need['a'] = 1, need['b'] = 1, found = 1; i = 0, j = 1 : 'a', need['a'] = 0, need['b'] = 1, found = 2;i = 0, j = 2 : 'a', need['a'] = -1, need['b'] = 1, found = 2;i = 0, j = 3 : 'b', need['a'] = -1, need['b'] = 0, found =3 == t.length() we find a valid window. However, this window maybe too large. We look from the i to see whether we can reduce the window size given a fixed j.look from left:when i = 0: remove one 'a', need['a'] = 0whem i = 1, remove one 'a', need['a'] = 1 > 0, we can not move this 'a', which means we can not make the window size smaller. This is a smallest window size given the j. We get the answer.class Solution {public:    string minWindow(string s, string t)     {        vector<int> m(128,0);        for(auto c: t) m[c]++;        int cnt = t.length(), i = 0, j = 0, d = INT_MAX, head = 0;        while( j < s.length())        {            if(m[s[j]] > 0 )             {                 cnt--;            }            m[s[j]]--;++j;            while(cnt == 0) // valid result            {                if(j - i  < d)  {d = j - i; head = i;}                m[s[i]]++;                if(m[s[i]] == 1) cnt++;  //make it invalid                ++i;            }          }        return d==INT_MAX? "":s.substr(head, d);     }};`
`class Solution {public:    string minWindow(string s, string t)     {        const int N = s.length(), M = t.length();        vector<int> n(128, 0), m(128,0);        for(auto c: t) m[c]++;        int cnt = 0, i = 0, j = 0, d = INT_MAX, head = 0;        while( j < s.length())        {            if(n[s[j]] < m[s[j]])             {                 cnt++;            }            n[s[j]]++;++j;            while(cnt == M) // valid result            {                if(j - i  < d)  {d = j - i; head = i;}                if(n[s[i]] ==  m[s[i]]) cnt--;  //make it invalid                n[s[i]]--;                ++i;            }          }        return d==INT_MAX? "":s.substr(head, d);     }};`

We can also rewrite the code by using for loops instead of while loop.

`class Solution {public:    string minWindow(string s, string t)     {        const int N = s.length(), M = t.length();        vector<int> n(128, 0), m(128,0);        for(auto c: t) m[c]++;        int cnt = 0, i = 0, j = 0, d = INT_MAX, head = 0;        for (int j = 0; j < N; ++j)        {            auto c = s[j];            if(n[c] < m[c]) cnt++;            n[c]++;            while(cnt == M) // valid result            {                if(j - i +1  < d)  {d = j - i + 1; head = i;}                if(n[s[i]] ==  m[s[i]]) cnt--;  //make it invalid                n[s[i]]--;                ++i;            }          }        return d==INT_MAX? "":s.substr(head, d);     }};`

# Reference

Data Scientist/MLE/SWE @takemobi

## More from Jimmy Shen

Data Scientist/MLE/SWE @takemobi