1
class Solution {
2
 public:
3
  string smallestSubsequence(string s) {
4
    string st = "";
5
    unordered_map<char, int> m;
6
    vector<bool> vis(26, false);
7
    for (int i = 0; i < s.size(); i++) m[s[i]]++;
8

9
    stack<char> t;
10

11
    t.push(s[0]), m[s[0]]--;
12
    st += s[0];
13
    vis[s[0] - 'a'] = true;
14

15
    for (int i = 1; i < s.size(); i++) {
16
      m[s[i]]--;
17
      if (!vis[s[i] - 'a']) {
18
        while (!t.empty() && m[t.top()] > 0 && t.top() > s[i]) {
19
          st.pop_back();
20
          vis[t.top() - 'a'] = false;
21
          t.pop();
22
        }
23
        t.push(s[i]);
24
        vis[s[i] - 'a'] = true;
25
        st = st + s[i];
26
      }
27
    }
28
    return st;
29
  }
30
};