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

All Problems

All Solutions