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

class Solution {
public:
    // ori：存儲目標字符串t中各字符的出現次數（基準哈希表）
    // cnt：存儲當前滑動窗口中各字符的出現次數（動態哈希表）
    unordered_map<char, int> ori, cnt;

    // 檢查當前滑動窗口是否包含目標字符串t的所有字符，且各字符數量不小於t中的數量
    bool check() { 
        // 遍歷目標哈希表ori中的每個字符
        for (const auto &p : ori) { 
            // 如果當前窗口中該字符的數量小於目標數量，説明窗口不滿足條件
            if (cnt[p.first] < p.second) { 
                return false;
            }
        }
        // 所有字符都滿足數量要求，窗口有效
        return true; 
    }

    // 尋找s中包含t所有字符的最小長度子串
    string minWindow(string s, string t) {
        // 初始化目標哈希表ori：統計t中每個字符的出現次數
        for (const auto &c : t) { 
            ++ori[c];
        }

        // l：滑動窗口左邊界，r：滑動窗口右邊界（初始化為-1，方便首次++r指向0）
        int l = 0, r = -1; 
        // len：當前找到的最小窗口長度（初始化為最大值）
        // ansL：最小窗口的起始索引，ansR：最小窗口的結束索引（初始化為-1表示未找到）
        int len = INT_MAX, ansL = -1, ansR = -1; 

        // 右指針遍歷整個字符串s（當r小於s長度時持續循環）
        while (r < int(s.size())) { 
            // 右指針右移一位（首次循環會從-1移到0）
            // 如果當前字符是t中包含的字符（存在於ori中），則在cnt中增加其計數
            if (ori.find(s[++r]) != ori.end()) { 
                ++cnt[s[r]];
            }

            // 當窗口滿足條件（包含t所有字符），且左指針不超過右指針時，嘗試收縮左邊界以尋找更小窗口
            while (check() && l <= r) { 
                // 計算當前窗口長度，若小於已知最小長度，則更新最小長度和窗口索引
                if (r - l + 1 < len) { 
                    len = r - l + 1;
                    ansL = l; // 記錄當前窗口的起始位置
                }
                // 如果左邊界字符是t中包含的字符，移除它時需要減少cnt中的計數
                if (ori.find(s[l]) != ori.end()) { 
                    --cnt[s[l]];
                }
                // 左指針右移，收縮窗口
                ++l;
            }
        }

        // 如果未找到有效窗口（ansL仍為-1），返回空字符串；否則返回最小窗口子串
        return ansL == -1 ? string() : s.substr(ansL, len);
    }
};