76. Minimum Window Substring

class Solution {
public:
    string minWindow(string s, string t)
    {
        if (s.size() == 0 || t.size() == 0) return "";

        int left = 0;

        // 當前窗口中已匹配的字元數量
        int cnt = 0;

        // 最小子字串的起始位置
        int minLeft = -1;

        // 最小子字串的長度
        int minLen = INT_MAX;

        // 計算字元出現的頻率
        unordered_map<char, int> m;
        for (auto& c : t) ++m[c];

        for (int right = 0; right < s.size(); ++right)
        {
            // 如果 --m[s[right]] >= 0
            // 代表是目標字元，則 ++cnt
            if (--m[s[right]] >= 0)
            {
                ++cnt;
            }

            // 當 cnt == t.size() 的時候，代表子字串都有覆蓋到 t 的字母了
            while (cnt == t.size())
            {
                // 則計算當前的長度
                int curLen = right - left + 1;

                // 如果發現當前的長度更小，則
                if (minLen > curLen)
                {
                    // 更新 minLen 的值
                    minLen = curLen;

                    // 最小左邊界等於 left
                    minLeft = left;
                }

                // 如果發現左邊界是 t 其中一個字母
                // 則頻率 + 1 回來，且計數 cnt - 1
                if (++m[s[left]] > 0) --cnt;

                // 最後更新左邊界
                ++left;
            }
        }
        return minLeft == -1 ? "" : s.substr(minLeft, minLen);
    }
};

• T: $O(∣S∣+∣T∣)$
• S: $O(∣S∣+∣T∣)$