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 <= text.length <= 1000
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();
}
}