Binary search and two pointers

LeetCode 76 Minimum Window Substring

76. Minimum Window Substring

Binary search get AC (time complexity O(128 n log n))

runtime

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.

code

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

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.

code

count down

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'] = 0
whem 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); 
    }
};

counter up

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); 
    }
};

count up another way to write the code

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

[1]https://leetcode.com/problems/minimum-window-substring/discuss/26808/Here-is-a-10-line-template-that-can-solve-most-'substring'-problems