LeetCode 76. Minimum Window Substring

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    string minWindow(string s, string t) {
        int n1 = s.size(), n2 = t.size();
        if (n1 < n2) return "";
        vector<int> freq(128);
        for (char c : t)
            freq[c]++;
        int left = 0, right = 0, minWinLen = INT_MAX, head = 0;
        while (right < n1) {
            if (freq[s[right++]]-- > 0)
                --n2; // char in t.
            while (n2 == 0) { // valid window.
                if (right - left < minWinLen)
                    minWinLen = right - (head = left); // get min window length.
                if (freq[s[left++]]++ == 0)
                    n2++;
            }
        }
        return minWinLen == INT_MAX ? "" : s.substr(head, minWinLen);
    }
};