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;
    }
};