1081. 不同字符的最小子序列

思路

給定一個字串，比如 $abcb$ ，要求回傳 $abc$ ，回傳的字串不能有重複字元，並且跟在原字串的順序是一樣的。
上面的例子當中，重複出現了兩次 $b$ ，那麼就能刪掉其中一個 $b$ 作為參考答案。

• 刪掉第一個 $b$ ， $acb$
• 刪掉第二個 $b$ ， $abc$

這兩個方案中，第二個方案最後答案的字典序比較小，所以選它。

假如現在的字串是 $abc$

• 來了一個 $d$ ，因為 $d$ 的字典序比較大，放的越後面越好，加到最後一個位置是最好的，直接變成 $abcd$ 。
• 如果來的不是 $d$ 是 $a$ ，他應該要放的越前面越好，所以試著踢掉前面的 $bc$ ，

不過踢掉之後，需要確保後面有其他的 $bc$ ，讓最後的結果依舊有這些字元，遍歷到後面的 $bc$ 時，再讓它們進來就好。
因此把字串本身當作單調棧，去做上面的操作。

• freq[26]紀錄剩下還有多少字元會進來。
• have[26]紀錄當前答案當中是否有出現字元。

所有操作用單調棧去做，過程盡量維持嚴格遞增，除非被踢的字元後面不出現。

程式碼

單調棧

class Solution {
public:
    string smallestSubsequence(string s) {
        int freq[26]{}, have[26]{};
        for(char ch : s) {
            freq[ch - 'a']++;
        }
        int n = s.length();
        string res;
        for(char ch : s) {
            freq[ch - 'a']--; // 剩下的字元變少了
            if(have[ch - 'a']) continue; // 答案中已經包含該字元，不需要再加
            while(!res.empty() && res.back() > ch && freq[res.back() - 'a']) {
                // 如果新加入的字元比前面字典序小，試著踢掉它
                // 後面被踢的字元如果還會出現，那就踢掉。
                have[res.back() - 'a'] = false;
                res.pop_back();
            }
            res += ch;
            have[ch - 'a'] = true;
        }
        return res;
    }
};
/*
如果現在的字串 abc, 來了一個 d, 欣然接受 -> abcd 
如果來了一個 a, 最好的方式是 aa, 但是要確保丟掉的 bc 後面能加回來
*/

複雜度分析

• 時間複雜度：$O(n)$
• 空間複雜度：$O(n)$