Problem:316. 去除重复字母

思路：先统计每个字母出现的次数，从左到右遍历数组，我们很容易想到，如果遇到了一个比当前答案末尾字母小的字母的话，那么如果后面还有这个答案末尾比较大的字母，我们可以把末尾字母去掉让新的字母加进来，直到遇到比他小的字母或者不能去除的字母。

变形题

Accode:

class Solution {
public:
    string removeDuplicateLetters(string s) {
        unordered_map<char,int> cnts;
        vector<bool> in_ans(26,false);
        for(auto item:s){
            cnts[item]++;
        }
        vector<char> ans;
        for(int i=0;i<s.length();i++){
            cnts[s[i]]--;
            if(in_ans[s[i]-'a']) continue;

            while(ans.size() && ans.back()>s[i]){
                if(cnts[ans.back()]==0) break;
                in_ans[ans.back()-'a'] = false;
                ans.pop_back();
            }
            ans.push_back(s[i]);
            in_ans[s[i]-'a'] = true;
        }
        return string(ans.begin(),ans.end());
    }
};

时间复杂度：$o(n)$