// 演算法：與 C 版相同的單調堆疊 + 貪心。這裡用 std::string 當堆疊，
// 用 back()/pop_back()/push_back() 操作末端，程式碼更貼近 C++ 慣用寫法。
// Algorithm: same monotonic-stack greedy as the C version, but using std::string as
// the stack and its back()/pop_back()/push_back() helpers for idiomatic C++.
class Solution {
public:
    string smallestSubsequence(string s) {
        vector<int> remaining(26, 0);  // 每個字母後面還剩幾個 / how many of each letter remain
        vector<bool> inStack(26, false); // 是否已在結果中 / whether a letter is already in the result

        // 先算出每個字母的總數。/ First, count every letter's total occurrences.
        for (char ch : s)              // range-for：直接依序取出每個字元 / range-for iterates each char
            remaining[ch - 'a']++;     // ch-'a' 把字母轉成 0..25 的索引 / map letter to index 0..25

        string stack;                  // 用字串當堆疊，末端就是堆疊頂端 / a string used as a stack; its end is the top

        for (char ch : s) {
            int c = ch - 'a';          // 當前字母索引 / index of current letter
            remaining[c]--;            // 經過一個，後面剩餘減一 / one fewer remains to the right

            if (inStack[c]) continue;  // 已在堆疊就跳過 / skip if already present

            // 頂端比 ch 大且後面還會出現，就彈出頂端。
            // Pop the top while it is larger than ch and still occurs later.
            while (!stack.empty()                       // 堆疊非空 / not empty
                   && stack.back() > ch                 // 頂端字母較大 / top is larger
                   && remaining[stack.back() - 'a'] > 0) { // 頂端後面還有 / it recurs later
                inStack[stack.back() - 'a'] = false;    // 清除被彈出者的標記 / clear its flag
                stack.pop_back();                       // 移除末端字元（彈出）/ remove last char (pop)
            }

            stack.push_back(ch);   // 把當前字母加到末端（推入）/ append current letter (push)
            inStack[c] = true;     // 標記為已在堆疊 / mark as present
        }

        return stack;  // 字串本身就是答案 / the string itself is the answer
    }
};