1. 题目

给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证 返回结果的字典序最小（要求不能打乱其他字符的相对位置）。

注意：该题与 1081 https://leetcode-cn.com/problems/smallest-subsequence-of-distinct-characters 相同

示例 1： 输入：s = "bcabc" 输出："abc"

示例 2： 输入：s = "cbacdcbc" 输出："acdb"

提示： 1 <= s.length <= 104 s 由小写英文字母组成

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/remove-duplicate-letters 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题思路

这题与402 移掉K位数字类似

不同的是402总共去除K位数字，最后可以有重复的；而这题要去除所有的重复字母，未重复的字母不能去除。

因此这题不能简单的像402一样，每次去除第一个降序序列的首位，因为存在着这样的特殊情况：该首位字母只剩下这一个了，还有一些其他的问题。

这里举个例：absadfbs

如果按照之前的算法，那么：absadfbs => abadfbs => aadfbs => adfbs

很遗憾，最后的正确答案是abdfs

那么，如何修改

前面我们每次去除第一个降序序列的首位，原因是若要使得剩下的数字最小，需要保证靠前的数字尽可能小。

那么这里应该为对于最终返回的字符串，靠前的字符是在能保证其他字符至少能出现一次情况下的最小字符。

利用哈希表amt(key,value)，表示字符key出现的次数为value

1. 对于字符s[i+1]，若小于等于字符s[i]，同时字符s[i]去掉后能保证还能出现至少一次，则去掉较大的字符s[i]，因为要使得靠前的字符尽量小。
2. 对于字符s[i+1]，若在[0,i]间出现过，则去掉靠后的字符，因为上一个条件已经保证了前面出现过的相同的字符s[j]在一个更大的字符c的前面（*s[j] c*），如果去掉靠前的字符（*c*s[i+1]），很显然字典序（*s[j] c* >*c*s[i+1] ），因为c>s[i+1]=s[j]。

同样的，可以利用单调栈来优化

3. 代码

class Solution {
public:
    string removeDuplicateLetters(string s) {
        unordered_map<char,int> amt;//char c 's amount => int i
        for(auto &x:s) amt[x]++;
        for(int i=0;i<s.size()-1;++i){
            if(s.find(s[i+1],0)<i+1) {
                amt[s[i+1]]--;
                s.erase(i+1,1);
                i-=1;
            }
            else if( s[i]>=s[i+1] && amt[s[i]]>1){
                amt[s[i]]--;
                s.erase(i,1);
                i-2>=0?i=i-2:i=-1;
            }
        }
        if(amt[s.back()]>1) s.pop_back();
        return s;
    }
};

3.1. 单调栈优化

（这里用vector代替了栈）

class Solution {
public:
    string removeDuplicateLetters(string s) {
        unordered_map<char,int> amt;//char c 's amount => int i
        for(auto &x:s) amt[x]++;

        vector<char> res;
        for(int i=0;i<s.size();++i){
            if(!res.empty() && find(res.begin(),res.end(),s[i])!=res.end()){
                amt[s[i]]--;
                continue;
            }
            while(!res.empty() && s[i]<res.back() && amt[res.back()]>1){
                amt[res.back()]--;
                res.pop_back();
            }
            res.push_back(s[i]);
        }
        s="";
        for(auto &x:res) s+=x;
        return s;
    }
};