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.

class Solution {
    public String smallestSubsequence(String S) {
        // Use a stack to keep the characters for result.
        Stack<Integer> stack = new Stack<>();
        int[] last = new int[26], seen = new int[26];
        // Find the index of last occurrence for each character.
        for (int i = 0; i < S.length(); i++)
            last[S.charAt(i) - 'a'] = i;
        // 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.
        for (int i = 0; i < S.length(); ++i) {
            int c = S.charAt(i) - 'a';
            if (seen[c]++ > 0)
                continue;
            while (!stack.isEmpty() && stack.peek() > c && i < last[stack.peek()])
                seen[stack.pop()] = 0;
            stack.push(c);
        }
        StringBuilder sb = new StringBuilder();
        for (int i : stack)
            sb.append((char) ('a' + i));
        return sb.toString();
    }
}