Window String

• Time : $O(|A| + |B|)$
• Space : $O(1)$

c++

string Solution::minWindow(string A, string B) {
    unordered_map<char,int> freq;
    for(auto b : B) freq[b]++;
    unordered_map<char,int> ffreq;
    int l = 0, r = 0, match = 0, n = A.length();
    int cut = -1, len = INT_MAX;
    while(r < n) {
        while(r < n and match < freq.size()) {
            ++ffreq[A[r]];
            if(freq.count(A[r]) and freq[A[r]] == ffreq[A[r]]) match++;
            r++;
        }
        while(l < r and match == freq.size()) {
            if(r - l < len) {
                len = r - l;
                cut = l;
            }
            --ffreq[A[l]];
            if(freq.count(A[l]) and freq[A[l]] - 1 == ffreq[A[l]]) match--;
            l++;
        }
    }


    return len == INT_MAX ? "" : A.substr(cut,len);
}