Formatted question description: https://leetcode.ca/all/1081.html

1081. Smallest Subsequence of Distinct Characters (Medium)

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

Example 1:

Input: "cdadabcc"
Output: "adbc"

Example 2:

Input: "abcd"
Output: "abcd"

Example 3:

Input: "ecbacba"
Output: "eacb"

Example 4:

Input: "leetcode"
Output: "letcod"

Note:

1 <= text.length <= 1000
text consists of lowercase English letters.

Solution 1.

// OJ: https://leetcode.com/problems/smallest-subsequence-of-distinct-characters/
// Time: O(N)
// Space: O(1)
class Solution {
public:
    string smallestSubsequence(string text) {
        int cnts[26] = {0}, used[26] = {0};
        for (char c : text) ++cnts[c - 'a'];
        string ans;
        for (char c : text) {
            cnts[c - 'a']--;
            if (used[c - 'a']) continue;
            while (ans.size() && cnts[ans.back() - 'a'] && c < ans.back()) {
                used[ans.back() - 'a'] = 0;
                ans.pop_back();
            }
            ans.push_back(c);
            used[c - 'a'] = 1;
        }
        return ans;
    }
};

Java

class Solution {
    public String smallestSubsequence(String text) {
        Map<Character, Integer> map = new HashMap<Character, Integer>();
        int length = text.length();
        for (int i = 0; i < length; i++) {
            char c = text.charAt(i);
            map.put(c, i);
        }
        Set<Character> set = new HashSet<Character>();
        Stack<Character> stack = new Stack<Character>();
        for (int i = 0; i < length; i++) {
            char c = text.charAt(i);
            if (set.contains(c))
                continue;
            while (!stack.isEmpty() && stack.peek() > c) {
                int lastIndex = map.get(stack.peek());
                if (lastIndex > i) {
                    char prevC = stack.pop();
                    set.remove(prevC);
                } else
                    break;
            }
            set.add(c);
            stack.push(c);
        }
        StringBuffer sb = new StringBuffer();
        while (!stack.isEmpty())
            sb.append(stack.pop());
        sb.reverse();
        return sb.toString();
    }
}

```
Todo
```

# 1081. Smallest Subsequence of Distinct Characters
# https://leetcode.com/problems/smallest-subsequence-of-distinct-characters/

class Solution:
    def smallestSubsequence(self, s: str) -> str:
        counter, visited, stack = collections.Counter(s), set(), []
        
        for c in s:
            counter[c] -= 1
            if c in visited: continue
            
            while stack and stack[-1] > c and counter[stack[-1]] > 0:
                visited.remove(stack.pop())
            
            visited.add(c)
            stack.append(c)
        
        return "".join(stack)

1081 - Smallest Subsequence of Distinct Characters

1081. Smallest Subsequence of Distinct Characters (Medium)

Solution 1.

All Problems

All Solutions