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.

Solution: Using sliding window

First we need an array to store the count of target string. Second we need an array to store the count of the sliding window. We also need a left pointer, valid account in sliding window, and the current min length.

We iterate throught the source string, the index i is the right pointer. Everytime we meet a char in target string, we update source count array and valid count.

After that, if the window's valid count is equal to target size, we find a match. We update the min length first, and then update source count array and valid count, move the left pointer forward by 1.

    string minWindow(string S, string T) {
        if (T.size() > S.size()) return "";

        string res = "";
        int left = 0, count = 0, minLen = S.size() + 1;
        int m1[256] = {0}, m2[256] = {0};
        for (auto ch: T) m1[ch]++;

        for (int right = 0; right < S.size(); ++right) {
            if (m1[S[right]] == 0) continue;

            m2[S[right]]++;
            if (m2[S[right]] <= m1[S[right]]) ++count;

            while (count == T.size()) {
                // Update min window
                if (right - left + 1 < minLen) {
                    minLen = right - left + 1;
                    res = S.substr(left, minLen);
                }

                if (m1[S[left]] != 0) {
                    m2[S[left]] -= 1;
                    if (m2[S[left]] < m1[S[left]]) count -= 1;
                }
                left += 1;
            }
        }
        return res;
    }