Binary search and two pointer

76. Minimum Window Substring

binary search

We can use a binary search to solve this problem. The idea is pretty straightforward. Explore different legth to see whether it works. In order to speed up, prefix sum is also used.

58 is the scope of the acsii code from A to z.

class Solution {
public:
    bool good(int mid,   vector<vector<int>> &frequency,  vector<int>& cnt){
        for (int i = mid; i <frequency.size(); ++i){
            bool found = true;
            for (int k = 0; k < 58; ++k){
                if (cnt[k]  > frequency[i][k] - frequency[i - mid][k]) {
                    found = false;
                    break;
                }
            }
            if (found) return true;
        }
        return false;
    }
    string find_(int mid,   vector<vector<int>> &frequency,  vector<int>& cnt, string s){
        string ret = "";
        for (int i = mid; i <frequency.size(); ++i){
            bool found = true;
            for (int k = 0; k < 58; ++k){
                if (cnt[k]  > frequency[i][k] - frequency[i - mid][k]) {
                    found = false;
                    break;
                }
            }
            if (found) return s.substr(i - mid, mid);
        }
        return ret;
    }
    string minWindow(string s, string t) {
        int l = t.size(), r = s.size();
        const int n = s.size();
        string ret = "";
        vector<vector<int>> frequency(n + 1, vector<int>(58, 0));
        
        for (int i = 0; i < n; ++i){
            frequency[i+1] = frequency[i];
            frequency[i+1][s[i]-'A']++;
        }
        vector<int> cnt(58, 0);
        for (auto x: t)cnt[x-'A']++;
        while (l < r){
            int mid = (l + r) / 2;
            if (good(mid, frequency, cnt)){
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        if (good(l, frequency, cnt))return find_(l, frequency, cnt, s);
        return ret;
        
    }
};

We can also use two pointer to solve this problem

/*
L ------------------------ R , Suppose this is the window that contains all characters of T 
                          
        L----------------- R , this is the contracted window. We found a smaller window that still contains all the characters in T

When the window is no longer valid, start expanding again using the right pointer.
*/
class Solution {
public:
    string minWindow(string s, string t) {
        unordered_map<int, int> m;
        for (auto x: t)m[x]++;
        unordered_set<int> characters;
        for (auto [ch, v]: m) characters.insert(ch);
        string ret = "";
        const int n = s.size();
        int j = 0;
         unordered_map<int, int> curr_m;
        for (int i = 0; i < n; ++i){
            if (m.find(s[i]) == m.end())continue;
            curr_m[s[i]]++;
            if (curr_m[s[i]] == m[s[i]]) characters.erase(s[i]);
            while (characters.empty() && j <= i){
                if (ret.empty() || i - j + 1 < ret.size()){
                    ret = s.substr(j, i - j + 1);
                }
                if (m.find(s[j]) == m.end()){
                    j++;
                    continue;
                }
                else {
                    curr_m[s[j]]--;
                    if (curr_m[s[j]] < m[s[j]]){
                        characters.insert(s[j]);
                    }
                    j++;
                }  
            }
        }
        return ret;
    }
};

Reference

[1]https://jimmy-shen.medium.com/binary-search-and-two-pointers-ec3ca697744