// 演算法 / Algorithm: 滑動視窗 (sliding window)。
// 右指針擴張視窗直到覆蓋 t；覆蓋後收縮左指針求最短，過程中記錄最短合格視窗。
// Expand right until the window covers t; then shrink from the left to minimize,
// recording the shortest valid window. Each char is visited at most twice → O(m+n).

char* minWindow(char* s, char* t) {
    // 取得兩字串長度 / get the lengths of both strings.
    // strlen 會掃到結尾的 '\0'，所以先算好避免重複計算 / cache lengths to avoid recomputing.
    int m = 0; while (s[m] != '\0') m++;   // 手算 s 長度 / count s manually
    int n = 0; while (t[n] != '\0') n++;   // 手算 t 長度 / count t manually

    // 若 t 比 s 長，s 絕不可能覆蓋 t，直接回傳空字串
    // If t is longer than s, no window can cover it → return "".
    if (n == 0 || m < n) {
        char* empty = (char*)malloc(1);    // 配置 1 byte 放結尾符 / 1 byte for the terminator
        empty[0] = '\0';                   // C 字串以 '\0' 結尾 / C strings end with '\0'
        return empty;
    }

    // need[c]：t 中字元 c 還需要幾個 / how many of char c are still required.
    // have[c]：目前視窗中字元 c 有幾個 / how many of char c are in the window now.
    // 大小 128 可覆蓋所有 ASCII 字母 / size 128 covers all ASCII letters.
    int need[128] = {0};                   // 全部初始化為 0 / initialize all to 0
    int have[128] = {0};

    // 統計 t 中每個字元的需求量 / tally how many of each char t needs.
    // (unsigned char) 轉型避免負索引（若有非 ASCII） / cast guards against negative indexing.
    for (int i = 0; i < n; i++)
        need[(unsigned char)t[i]]++;

    // required：t 中不同字元的種類數 / number of DISTINCT chars in t.
    int required = 0;
    for (int c = 0; c < 128; c++)
        if (need[c] > 0) required++;

    // formed：視窗中「次數已達標」的不同字元數 / distinct chars already satisfied.
    // 當 formed == required 時，視窗就覆蓋了整個 t / window covers t when these are equal.
    int formed = 0;

    int left = 0;                          // 視窗左端 / left edge of window
    int bestLen = m + 1;                   // 最短合格長度，初始設成不可能的大值 / best length, start huge
    int bestStart = 0;                     // 最短視窗的起點 / start index of best window

    // right 從 0 掃到 m-1，逐一把字元加進視窗 / right scans s, absorbing one char each step.
    for (int right = 0; right < m; right++) {
        unsigned char c = (unsigned char)s[right];  // 取出右端字元 / the char entering the window
        have[c]++;                                  // 視窗中該字元數 +1 / its count goes up

        // 若這個字元剛好讓某需求被「填滿」(不多不少)，formed +1
        // If this char's count just reached exactly what t needs, one more char is satisfied.
        if (need[c] > 0 && have[c] == need[c])
            formed++;

        // 視窗已覆蓋 t 時，盡量從左邊收縮以求最短
        // While the window is valid, shrink from the left to minimize it.
        while (formed == required) {
            int curLen = right - left + 1;          // 目前視窗長度 / current window length
            if (curLen < bestLen) {                 // 發現更短的合格視窗就記下來 / record if shorter
                bestLen = curLen;
                bestStart = left;
            }

            unsigned char lc = (unsigned char)s[left]; // 即將被移出視窗的左端字元 / char leaving
            have[lc]--;                                // 視窗中該字元數 -1 / its count drops
            left++;                                    // 左端右移，視窗縮小 / move left edge inward

            // 若移除後該字元數低於需求，視窗不再合格，formed -1，迴圈結束
            // If removing it drops below the need, the window is no longer valid → stop shrinking.
            if (need[lc] > 0 && have[lc] < need[lc])
                formed--;
        }
    }

    // 從沒找到合格視窗 → bestLen 仍是初始值 → 回傳空字串
    // Never found a valid window → return "".
    if (bestLen == m + 1) {
        char* empty = (char*)malloc(1);
        empty[0] = '\0';
        return empty;
    }

    // 配置 bestLen+1 個 byte（多 1 個放結尾 '\0'）/ allocate bestLen+1 bytes (extra for '\0').
    char* result = (char*)malloc(bestLen + 1);
    for (int i = 0; i < bestLen; i++)
        result[i] = s[bestStart + i];      // 從 s 複製最短視窗的字元 / copy the best window out
    result[bestLen] = '\0';                // 補上結尾符，使其成為合法 C 字串 / terminate the string
    return result;                         // 呼叫者負責 free / caller frees this buffer
}