Skip to content

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<int> count(128);
    vector<bool> 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[string.ascii_lowercase.index(c)]:
        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)