76. Minimum Window Substring

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

Example:

Input: S = "ADOBECODEBANC", T = "ABC"
Output: "BANC"

Note:

• If there is no such window in S that covers all characters in T, return the empty string "".

• If there is such window, you are guaranteed that there will always be only one unique minimum window in S.

// Sliding window
string minWindow(string s, string t) { // time: O(m + n); space: (1)
    vector<int> record(128, 0);
    // initialization
    for (char c : t) ++record[c];
    int begin = 0, end = 0, head = 0, d = numeric_limits<int>::max(), counter = t.length();
    while (end < s.length()) {
        if (record[s[end++]]-- > 0) {
            counter--;
        }
        while (counter == 0) {
            if (end - begin < d) {
                head = begin;
                d = end - begin;
            }
            if (record[s[begin++]]++ == 0) {
                counter++;
            }
        }
    }
    return (d == numeric_limits<int>::max()) ? "" : s.substr(head, d);
}