Home
Algorithms Data Structures Interview Experiences
Amazon Google Facebook Microsoft Apple Netflix
Play 2048 How to

LeetCode Solutions

1081. Smallest Subsequence of Distinct Characters

Time: $O(n)$

Space: $O(n)$

			


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;
  }
};




			


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);
  }
}




			


class Solution:
  def smallestSubsequence(self, text: str) -> str:
    ans = []
    count = 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)