# 1081. Smallest Subsequence of Distinct Characters

• Time: $O(n)$
• Space: $O(n)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 class Solution { public: string smallestSubsequence(string text) { string ans; vector count(128); vector used(128); for (const char c : text) ++count[c]; for (const char c : text) { --count[c]; if (used[c]) continue; while (!ans.empty() && ans.back() > c && count[ans.back()] > 0) { used[ans.back()] = false; ans.pop_back(); } used[c] = true; ans.push_back(c); } return ans; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 class Solution { public String smallestSubsequence(String text) { StringBuilder sb = new StringBuilder(); int[] count = new int[128]; boolean[] used = new boolean[128]; for (final char c : text.toCharArray()) ++count[c]; for (final char c : text.toCharArray()) { --count[c]; if (used[c]) continue; while (sb.length() > 0 && last(sb) > c && count[last(sb)] > 0) { used[last(sb)] = false; sb.setLength(sb.length() - 1); } used[c] = true; sb.append(c); } return sb.toString(); } private char last(StringBuilder sb) { return sb.charAt(sb.length() - 1); } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 class Solution: def smallestSubsequence(self, text: str) -> str: ans = [] count = collections.Counter(text) used = [False] * 26 for c in text: count[c] -= 1 if used[ord(c) - ord('a')]: continue while ans and ans[-1] > c and count[ans[-1]] > 0: used[ord(ans[-1]) - ord('a')] = False ans.pop() ans.append(c) used[ord(ans[-1]) - ord('a')] = True return ''.join(ans)