1081. Smallest Subsequence of Distinct Characters.md

1081. Smallest Subsequence of Distinct Characters

---

Difficulty : Medium

Related Topics : String、Stack、Greedy

---

Return the lexicographically smallest subsequence of s that contains all the distinct characters of s exactly once.

Note: This question is the same as 316: https://leetcode.com/problems/remove-duplicate-letters/

Example 1:

Input: s = "bcabc"
Output: "abc"

Example 2:

Input: s = "cbacdcbc"
Output: "acdb"

Constraints:

• 1 <= s.length <= 1000
• s consists of lowercase English letters.

---

Solution

• mine
  • Java
    • Runtime: 1 ms, faster than 100.00%, Memory Usage: 37.2 MB, less than 11.55% of Java online submissions

      // O(N)time
      // O(1)space
      public String smallestSubsequence(String s) {
          char[] arr = s.toCharArray();
          int[] record = new int[26];
          boolean[] added = new boolean[26];
          for (char c : arr) {
              record[c - 'a']++;
          }
          LinkedList<Integer> list = new LinkedList<>();
          for (char c : arr) {
              int i = c - 'a';
              record[i]--;
              if (added[i]) continue;
      
              while(!list.isEmpty() && list.getLast() > i && record[list.getLast()] != 0) {
                  added[list.removeLast()] = false;
              }
              list.add(i);
              added[i] = true;
          }
      
          StringBuilder res = new StringBuilder();
          while (!list.isEmpty()) {
              res.append((char)('a' + list.removeFirst()));
          }
          return res.toString();
      }
      

---