Leetcode1081-smallestSubsequenceOfDistinctCharacters

Description

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

Example

Example 1:

Input: "cdadabcc"
Output: "adbc"

Example 2:

Input: "abcd"
Output: "abcd"

Example 3:

Input: "ecbacba"
Output: "eacb"

Example 4:

Input: "leetcode"
Output: "letcod"

Constraints:

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

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

Solution

class Solution {
    public String smallestSubsequence(String s) {
        if (s == null || s.length() <= 1) return s;
        Stack<Character> st = new Stack<>();    
        int[] set = new int[128];   //record if stack has the character
        int[] map = new int[128];   //record the number of characters remaining
        for (char ch: s.toCharArray()){
            map[ch]++;
        }
        
        for (char ch: s.toCharArray()){
            if (set[ch] > 0) {
                map[ch]--;
                continue;
            }
            while (!st.isEmpty() && ch < st.peek() && map[st.peek()] > 0){
                set[st.pop()] = 0;
            }
            st.push(ch);
            set[ch] = 1;
            map[ch]--;
        }
        
        StringBuilder res = new StringBuilder();
        while(!st.isEmpty())
            res.append(st.pop());
        
        return res.reverse().toString();
    }
}

---