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. 1 <= text.length <= 1000
  2. 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)
    
    

All Problems

All Solutions