贪心

从前往后遍历整个字符串，并用一个类似于栈来维护当前答案：

• 如果当前字符已经在当前答案中了，直接跳过。
• 如果没有，那么我们应该将这个字符加入答案中。但是为了字典序最小，我们需要考虑是否需要弹出栈顶元素。弹出的条件则是：当前元素小于栈顶元素，并且当前栈顶元素还在后面出现过，那么栈顶元素在后面再加进来会得到更小的字典序。

需要用两个map，一个map表示该字母是否已经在答案中，另外一个map表示原串字母最后出现的位置。

时间复杂度$O(N)$，空间复杂度$O(N)$

AC代码

class Solution {
public:
    string removeDuplicateLetters(string s) {
        string res;
        unordered_map<char,bool> is_in;
        unordered_map<char,int> last;
        //预处理每个字母最后出现的位置
        for (int i = 0 ; i < s.size() ; i ++) last[s[i]] = i;

        for (int i = 0 ; i < s.size() ; i ++) {
            if (is_in[s[i]]) continue;
            while (res.size() && res.back() > s[i] && last[res.back()] > i) {
                is_in[res.back()] = false;
                res.pop_back();
            }
            is_in[s[i]] = true;
            res += s[i];
        }
        return res;
    }
};