1
class Solution {
2
  public String smallestSubsequence(String s) {
3
    boolean[] inStack = new boolean[26];
4
    int[] lastIdx = new int[26];
5
    Arrays.fill(lastIdx, -1);
6
    for (int i = 0; i < s.length(); i++) {
7
      lastIdx[s.charAt(i) - 'a'] = i;
8
    }
9
    Deque<Character> dq = new ArrayDeque<>();
10
    for (int i = 0; i < s.length(); i++) {
11
      char ch = s.charAt(i);
12
      if (inStack[ch - 'a']) {
13
        continue;
14
      }
15
      while (!dq.isEmpty() && dq.peekLast() > ch && lastIdx[dq.peekLast() - 'a'] > i) {
16
        inStack[dq.pollLast() - 'a'] = false;
17
      }
18
      dq.addLast(ch);
19
      inStack[ch - 'a'] = true;
20
    }
21
    StringBuilder sb = new StringBuilder();
22
    while (!dq.isEmpty()) {
23
      sb.append(dq.pollFirst());
24
    }
25
    return sb.toString();
26
  }
27
}