76. Minimum Window Substring

Input:  s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"

// 演算法 / 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 會掃到結尾的 ''，所以先算好避免重複計算 / cache lengths to avoid recomputing.
    int m = 0; while (s[m] != '') m++;   // 手算 s 長度 / count s manually
    int n = 0; while (t[n] != '') 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] = '';                   // C 字串以 '' 結尾 / C strings end with ''
        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] = '';
        return empty;
    }

    // 配置 bestLen+1 個 byte（多 1 個放結尾 ''）/ allocate bestLen+1 bytes (extra for '').
    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] = '';                // 補上結尾符，使其成為合法 C 字串 / terminate the string
    return result;                         // 呼叫者負責 free / caller frees this buffer
}

// 演算法 / 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);
    }
};