Smallest Subsequence of Distinct Characters

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"
 

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:


Explanation:


Find the index of last occurrence for each character.
Use a stack to keep the characters for result.
Loop on each character in the input string S,
if the current character is smaller than the last character in the stack,
and the last character exists in the following stream,
we can pop the last character to get a smaller result.



Time Complexity:


Time O(N)
Space O(26)

class Solution {
    public String smallestSubsequence(String text) {
        Stack<Integer> stack = new Stack<>();

        int[] last = new int[26], seen = new int[26];
        
        for (int i = 0; i < text.length(); i ++) {
            last[text.charAt(i) - 'a'] = i;
        }
        
        for (int i = 0; i < text.length(); i ++) {
            int c = text.charAt(i) - 'a';
            if (seen[c] ++ > 0) continue;
            while (!stack.isEmpty() && c < stack.peek() && last[stack.peek()] > i) {
                seen[stack.pop()] = 0;
            }
            stack.push(c);
        }
        
        StringBuilder sb = new StringBuilder();
        
        for (int i : stack) { 
            sb.append((char)('a' + i));
        }
        return sb.toString();
    }
}