1
class Solution {
2
 public:
3
  string removeDuplicateLetters(string s) {
4
    int len = s.size();
5
    string res = "";
6
    unordered_map<char, int> M;
7
    unordered_map<char, bool> V;
8
    stack<int> S;
9

10
    for (auto c : s) {
11
      if (M.find(c) == M.end())
12
        M[c] = 1;
13
      else
14
        M[c]++;
15
    }
16
    for (unordered_map<char, int>::iterator iter = M.begin(); iter != M.end(); iter++)
17
      V[iter->first] = false;
18

19
    cout << M.size() << V.size() << endl;
20
    for (int i = 0; i < len; i++) {
21
      M[s[i]]--;
22
      if (V[s[i]] == true) continue;
23

24
      while (!S.empty() and s[i] < s[S.top()] and M[s[S.top()]] > 0) {
25
        V[s[S.top()]] = false;
26
        S.pop();
27
      }
28
      S.push(i);
29
      V[s[i]] = true;
30
    }
31
    while (!S.empty()) {
32
      res = s[S.top()] + res;
33
      S.pop();
34
    }
35
    return res;
36
  }
37
};
38

39
Analysis Time complexity O(n)
40
space complexity O(n)