316. Remove Duplicate Letters

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 1:

Input: "bcabc"
Output: "abc"

Example 2:

Input: "cbacdcbc"
Output: "acdb"

利用一個int array來記錄每個字母出現的次數，另一個bool array紀錄字母是否已經被用過。先建立好dict array後再掃描input string一遍，每遇到一個字元，就在dict array裡面出現次數減一，接著檢查visited array看看是否已經利用過該字母，如果已經用過就continue。比較當前字母和res最後一個字母，如果當前字母的lexicographical order較小，且dict裡面對應的value不為0，代表之後還有這個字母能利用，所以可以把res最後一個字母的visited標記為false，把它pop掉，等之後遇到再加上。

// Greedy
string removeDuplicateLetters(string s) { // time: O(n); space: O(1)
    vector<int> dict(26, 0);
    vector<bool> visited(26, false);
    for (char ch : s) ++dict[ch - 'a'];
    string res;
    for (char ch : s) {
        int idx = ch - 'a';
        --dict[idx];
        if (visited[idx]) continue;
        while (ch < res.back() && dict[res.back() - 'a']) {
            visited[res.back() - 'a'] = false;
            res.pop_back();
        }
        res += ch;
        visited[idx] = true;
    }
    return res;
}