// 演算法：單調堆疊 + 貪心。由左到右掃描，用堆疊建構答案；
// 當堆疊頂端字母比當前字母大、且該字母後面還會再出現時就彈出，
// 讓較小字母提前，得到字典序最小的結果。
// Algorithm: monotonic-stack greedy. Scan left to right building the answer on a
// stack; pop a larger top letter when it still appears later, pulling smaller
// letters forward to reach the lexicographically smallest subsequence.

char* smallestSubsequence(char* s) {
    int remaining[26] = {0};   // 每個字母「後面還剩幾個」/ how many of each letter are still left
    int inStack[26]   = {0};   // 該字母是否已在堆疊中 / whether a letter is already on the stack

    // 第一次掃描：統計每個字母的總出現次數。
    // First pass: count total occurrences of each letter.
    for (int i = 0; s[i] != '\0'; i++)   // '\0' 是 C 字串結尾標記 / '\0' marks the end of a C string
        remaining[s[i] - 'a']++;         // s[i]-'a' 把 'a'..'z' 映成 0..25 / map letter to index 0..25

    // 用一個字元陣列當堆疊；最多 26 個不同字母，多留 1 格放結尾 '\0'。
    // Use a char array as the stack; at most 26 distinct letters, +1 for the terminator.
    char* stack = (char*)malloc(27 * sizeof(char));  // malloc 向作業系統要一塊記憶體 / allocate memory
    int top = 0;   // top 指向「下一個要寫入的位置」，也等於目前堆疊大小 / next write slot = current size

    // 第二次掃描：逐字元決定要不要彈出、要不要推入。
    // Second pass: for each character decide what to pop and whether to push.
    for (int i = 0; s[i] != '\0'; i++) {
        int c = s[i] - 'a';        // 當前字母的索引 0..25 / index of current letter
        remaining[c]--;            // 這個字元已被「經過」，後面剩餘數減一 / one fewer of it remains to the right

        if (inStack[c]) continue;  // 已在堆疊就跳過，每個字母只能一次 / skip if already present (one-time rule)

        // 只要頂端字母比 c 大、且頂端字母後面還會再出現，就彈出它。
        // While the top letter is larger than c AND still appears later, pop it.
        while (top > 0                             // 堆疊非空 / stack not empty
               && stack[top - 1] > s[i]            // 頂端字母比當前字母大 / top is lexicographically larger
               && remaining[stack[top - 1] - 'a'] > 0) {  // 頂端字母後面還有，彈掉安全 / it recurs later, safe to drop
            inStack[stack[top - 1] - 'a'] = 0;     // 清除被彈出字母的標記 / clear its in-stack flag
            top--;                                 // 彈出（縮小堆疊）/ pop by shrinking the stack
        }

        stack[top++] = s[i];   // 把當前字母推入堆疊，top 再前進一格 / push current letter, advance top
        inStack[c] = 1;        // 標記它已在堆疊中 / mark it as present
    }

    stack[top] = '\0';   // 補上字串結尾，讓它成為合法 C 字串 / terminate so it is a valid C string
    return stack;        // 回傳這塊記憶體；LeetCode 會負責釋放 / return the buffer (harness frees it)
}