316. Remove Duplicate Letters（贪心）

1.题目描述

Given a string which contains only lowercase letters, remove duplicate letters so that every letter appear once and only once. You must make sure your result is the smallest in lexicographical order among all possible results.

Example:

Given "bcabc"
Return "abc"
           

Given "cbacdcbc"
Return "acdb"
           

2.代码

分析：

1. 记录每个字符出现的次数，维护一个结果子串和已经添加过的子串的标记

2. 如果遇到一个字符，如果该字符已经添加过了那么不再添加；如果已有子串的尾字符 S 比当前字符F大，且 S 在剩余子串的次数大于1，那么可以考虑待到其后续到来时再放入结果子串中，用当前是字符F替换掉所有的这样的 S <script type="math/tex" id="MathJax-Element-645">S</script>，就能保证得到的子串是所有去重子串中的按字典序排序的最小子串（注意，不是要求子串是字典序排序）。

3. 如果上述不满足，那么直接将当前字符放入结果中（不满足条件的情况有2种：当前字符是第一个字符；尾字符剩余0个）

class Solution {
public:
    string removeDuplicateLetters(string s) {
        unordered_map<char, bool> visited;
        unordered_map<char, int> counter;
        string res = "";

        for(char c : s) counter[c]++;
        for(char c : s) {
            counter[c]--;
            if(visited[c]) continue;
            while(!res.empty() && (c < res.back() && counter[res.back()] > )) {
                visited[res.back()] = false;
                res.pop_back();
            }
            res += c;
            visited[c] = true;
        }   
        return res;
    }
};