题目描述

返回字符串 text 中按字典序排列最小的子序列，该子序列包含 text 中所有不同字符一次。

样例

输入："cdadabcc"
输出："adbc"

输入："abcd"
输出："abcd"

输入："ecbacba"
输出："eacb"

输入："leetcode"
输出："letcod"

注意

• 1 <= text.length <= 1000
• text 由小写英文字母组成。

算法

(贪心、单调栈) $O(n)$

1. 定义一个空的单调栈，从 text 的开头开始扫描。
2. 如果当前字符没有出现在栈中，并且栈首字符要大于当前字符，且栈首字符在当前位置之后仍然出现过，则将栈首出栈。直到栈空或符合规则后，当前字符进栈。
3. 如果当前字符出现在栈中，则不做处理。
4. 最终栈中元素的拼接就是答案。
5. 判断 栈首字符在当前位置之后仍然出现过，可以提前预处理出记录每个字符的出现次数，此时判断出现次数是否还大于 0 即可。

时间复杂度

• 单调栈每个字符最多进栈一次，出栈一次，判断的时间复杂度都是常数，故时间复杂度为 $O(n)$。

空间复杂度

• 需要额外的哈希表和栈空间，故空间复杂度为 $O(n)$。

C++ 代码

class Solution {
public:
    string smallestSubsequence(string text) {
        unordered_map<char, int> num;
        for (auto &c : text)
            num[c]++;

        stack<int> s;
        unordered_set<char> seen;
        for (auto &c : text) {
            num[c]--;
            if (seen.find(c) != seen.end())
                continue;
            while (!s.empty() && s.top() > c && num[s.top()] > 0) {
                seen.erase(s.top());
                s.pop();
            }
            s.push(c);
            seen.insert(c);
        }

        string ret;
        while (!s.empty()) {
            ret += s.top();
            s.pop();
        }
        reverse(ret.begin(), ret.end());
        return ret;
    }
};