1081. Smallest Subsequence of Distinct Characters

題目 / Problem

中文： 給定一個字串 s，回傳一個「字典序最小」的子序列，且該子序列要包含 s 中所有不同的字元，每個字元恰好出現一次。

「子序列」指的是：從原字串中刪掉零個或多個字元、但保持其餘字元原本的相對順序所得到的字串（不可以重新排列）。

English: Given a string s, return the lexicographically smallest subsequence of s that contains every distinct character of s exactly once.

A subsequence is what you get by deleting zero or more characters from the original string while keeping the remaining characters in their original relative order (you may not reorder them).

Constraints / 限制 - 1 <= s.length <= 1000 - s 只由小寫英文字母組成 / s consists of lowercase English letters.

Worked example / 範例 - Input: s = "cbacdcbc" - Output: "acdb" - 不同字元有 a, b, c, d 四個，輸出把每個各放一次，並且在所有合法排法中字典序最小。/ The distinct letters are a, b, c, d; the answer uses each once and is the smallest possible ordering that is still a valid subsequence.

名詞解釋 / Glossary

• 子序列 / Subsequence：保留原字串字元的相對順序，刪掉一些字元後得到的字串。例如 "ace" 是 "abcde" 的子序列，但 "aec" 不是（順序被打亂了）。
• 字典序 / Lexicographic order：像字典查字一樣，逐字元由左往右比較。第一個不同的位置上，字元較小者整體較小。例如 "acb" < "acd"，因為第三個字元 b < d。
• 貪心 / Greedy：每一步都做「當下看起來最好」的選擇，並證明這種局部最優能導向全域最優。
• 單調堆疊 / Monotonic Stack：一個堆疊（後進先出的容器），我們在放入元素前先彈出「破壞單調性」的元素，使堆疊內容維持某種遞增/遞減趨勢。這裡用來維持結果盡量遞增。
• 堆疊 / Stack：一種資料結構，只能從一端加入（push）與取出（pop），最後放入的最先取出（LIFO）。這裡我們把它當成正在建構的答案。
• 計數陣列 / Count array：一個長度 26 的陣列，記錄每個字母「後面還剩幾個」，用來判斷現在能不能安全地丟棄某字母。
• visited 標記 / in-stack flag：一個布林陣列，記錄某字母是否已經在答案堆疊裡，避免重複加入。

思路

中文：最直覺的暴力法是枚舉所有「包含全部不同字元各一次」的排列，檢查哪些是 s 的合法子序列，再取字典序最小者。但不同字元最多 26 種，排列數是階乘等級，完全不可行。我們需要更聰明的方法。關鍵觀察是：答案要字典序最小，就希望「越小的字母越靠前」。所以當我們由左到右掃描字串、逐步建構答案時，如果目前答案結尾是一個較大的字母 x，而現在遇到一個較小的字母 c，並且 x 在後面還會再出現，那我們就應該把 x 從答案中拿掉、讓 c 排到前面去——因為 x 之後補回來即可，而把小字母提前能讓字典序更小。這正是「單調堆疊 + 貪心」。我們維護一個堆疊當作正在建構的答案，同時用一個計數陣列記錄每個字母「後面還剩幾個」，用一個 visited 陣列記錄字母是否已在堆疊中。掃描到字元 c 時：先把它的剩餘計數減一；若 c 已在堆疊就跳過（每個字母只能出現一次）；否則，只要堆疊頂端字母比 c 大、且該頂端字母後面還會再出現（剩餘計數 > 0），就把它彈出（並清除 visited）；最後把 c 推入堆疊。彈出的兩個條件缺一不可：頂端比 c 大，才有替換成更小字典序的好處；頂端後面還有，才保證彈掉它以後仍能把它補回來、不會遺失字元。

English: The brute-force idea—generate every permutation of the distinct letters and keep the smallest one that is a valid subsequence—blows up factorially, so it is hopeless even for 26 letters. The smarter route comes from one observation: to be lexicographically smallest we want smaller letters as far left as possible. So we scan the string left to right and build the answer on a stack. Whenever the letter currently on top of the stack is larger than the incoming letter c, and that top letter still appears again later in the string, we pop it off—we can always re-add it later, and pulling the smaller letter forward makes the result smaller. This is the monotonic-stack greedy. We keep three things: a stack holding the answer under construction, a count array telling us how many of each letter remain to the right, and an in-stack boolean array so no letter is added twice. Processing a character c: decrement its remaining count; if c is already in the stack, skip it (each letter appears once); otherwise, while the stack top is greater than c and that top letter still occurs later (remaining count > 0), pop it (and clear its flag); then push c. Both pop conditions are essential: "top is greater" gives the lexicographic win, and "top occurs later" guarantees we can safely restore it, so no distinct letter is ever lost.

逐步走查 / Walkthrough

Example input s = "bcabc". 初始計數 / initial counts: a=1, b=2, c=2。stack 初始為空 / empty. in = all false.

最終堆疊由底到頂為 a,b,c，輸出 "abc"。/ Reading the stack bottom-to-top gives "abc". ✓

Solution — C

// 演算法：單調堆疊 + 貪心。由左到右掃描，用堆疊建構答案；
// 當堆疊頂端字母比當前字母大、且該字母後面還會再出現時就彈出，
// 讓較小字母提前，得到字典序最小的結果。
// 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] != ''; i++)   // '' 是 C 字串結尾標記 / '' 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 格放結尾 ''。
    // 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] != ''; 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] = '';   // 補上字串結尾，讓它成為合法 C 字串 / terminate so it is a valid C string
    return stack;        // 回傳這塊記憶體；LeetCode 會負責釋放 / return the buffer (harness frees it)
}

Solution — C++

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

複雜度 / Complexity

• Time: O(n) — n 是字串長度。雖然有 while 迴圈看似巢狀，但每個字元最多被推入堆疊一次、彈出一次，總操作量與 n 成正比（攤還分析）。/ Each character is pushed at most once and popped at most once, so the total work across all while iterations is linear despite the nested loop (amortized).
• Space: O(1) — 計數陣列與 in-stack 陣列都是固定 26 大小；堆疊最多存 26 個不同字母，與輸入長度無關，故為常數額外空間。/ The count and flag arrays are fixed size 26, and the stack holds at most 26 distinct letters, so the extra space is constant regardless of n.

Pitfalls & Edge Cases

• 兩個彈出條件缺一不可 / Both pop conditions are required：只有「頂端較大」還不夠——如果那個較大的字母後面不再出現，彈掉它就永遠補不回來，答案會缺字元。必須同時檢查 remaining > 0。/ "Top is larger" alone is unsafe; if that letter never appears again, popping it loses it forever. The remaining > 0 check prevents this.
• 重複字元只能加一次 / Skip letters already in the stack：若省略 inStack 檢查，同一字母可能被加入多次，違反「各出現一次」。if (inStack[c]) continue; 保證唯一性。/ Without the inStack skip, a letter could be added multiple times, breaking the once-each rule.
• 計數要在 continue 之前先減 / Decrement the count before the continue：即使當前字母已在堆疊、要跳過，也必須先做 remaining[c]--，否則後面「還剩幾個」會算錯，可能誤判某字母仍會出現。/ You must decrement even for skipped letters, or the remaining counts drift and pop decisions become wrong.
• 記得補 '\0'（C 版）/ Remember the terminator (C)：C 字串靠 '\0' 標記結尾；忘記寫會導致回傳時讀到越界的垃圾字元。/ A C string needs '\0]; forgetting it makes the caller read past the buffer.
• 配置足夠空間 / Allocate enough space (C)：最多 26 個字母加一個結尾，malloc(27) 剛好夠；配太小會緩衝區溢位。/ 26 letters plus terminator need 27 bytes; a smaller buffer overflows.
• 單一字元或全相同輸入 / Single or all-same input：例如 "aaaa"，答案是 "a"；程式第一個 a 推入，其餘因 inStack 而跳過，自然正確。/ For inputs like "aaaa" the answer is "a"; the first is pushed and the rest skipped, which the code handles naturally.