// 演算法 / Algorithm: 滑動視窗 (sliding window)，與 C 版相同邏輯。
// 用兩個 unordered_map 存「需求」與「視窗現況」，formed/required 判斷是否覆蓋 t。
// Expand right to cover t, shrink left to minimize, track the shortest valid window.
// Each character is processed at most twice → O(m + n).

#include <string>
#include <unordered_map>
#include <climits>   // INT_MAX
using namespace std;

class Solution {
public:
    string minWindow(string s, string t) {
        // 邊界：t 為空或比 s 長則不可能覆蓋 / impossible cases → empty result.
        if (t.empty() || s.size() < t.size()) return "";

        // unordered_map<char,int>：以字元為鍵、次數為值的雜湊表 / hash map char → count.
        // need 記錄 t 各字元需求量 / how many of each char t requires.
        unordered_map<char, int> need;
        for (char c : t) need[c]++;        // range-for：逐一遍歷 t 的字元 / iterate over t's chars

        unordered_map<char, int> have;     // 視窗目前各字元數量 / counts inside the window

        int required = (int)need.size();   // t 的不同字元種類數 / number of distinct chars in t
        int formed = 0;                    // 已滿足需求的不同字元數 / satisfied distinct chars

        int left = 0;                      // 視窗左端 / left edge
        int bestLen = INT_MAX;             // 最短合格長度，初始為極大值 / best length so far
        int bestStart = 0;                 // 最短視窗起點 / start of best window

        // right 為視窗右端，逐字擴張 / right edge advances one char at a time.
        for (int right = 0; right < (int)s.size(); right++) {
            char c = s[right];             // 進入視窗的字元 / entering char
            have[c]++;                     // 視窗中該字元數 +1 / bump its count

            // 若該字元次數剛好達標，formed +1
            // need.count(c) 檢查 c 是否是 t 需要的字元 / does t need this char?
            if (need.count(c) && have[c] == need[c])
                formed++;

            // 視窗覆蓋 t 時，從左邊盡量收縮 / shrink while the window stays valid.
            while (formed == required) {
                int curLen = right - left + 1;   // 目前視窗長度 / current length
                if (curLen < bestLen) {          // 更短就更新最佳解 / update best if shorter
                    bestLen = curLen;
                    bestStart = left;
                }

                char lc = s[left];               // 即將移出的左端字元 / char leaving the window
                have[lc]--;                      // 該字元數 -1 / drop its count
                left++;                          // 左端右移 / move left inward

                // 移除後低於需求 → 視窗失效 → formed -1，停止收縮
                // If it drops below the need, the window breaks → stop shrinking.
                if (need.count(lc) && have[lc] < need[lc])
                    formed--;
            }
        }

        // 找不到合格視窗則回空字串；否則用 substr 切出最短視窗
        // No valid window → ""; otherwise slice it out with substr(start, length).
        return bestLen == INT_MAX ? string("") : s.substr(bestStart, bestLen);
    }
};