Smallest Subsequence of Distinct Characters

Use a stack plus two pieces of bookkeeping: last[ch], the final index of each character, and inStack[ch]. Scan the string from left to right. If the current character is already in the stack, skip it because the result needs each character once. Otherwise, while the stack top is lexicographically larger than the current character and the top occurs again after this index, pop it and clear inStack for that character. It is safe to remove only characters that can be restored later. Then push the current character and mark it present. The stack at the end is the smallest lexicographic subsequence containing each distinct character exactly once. Each character enters and leaves at most once, so time is O(n) and extra space is O(alphabet size). The key proof is greedy: replace a larger earlier character with a smaller current one whenever the larger character remains available later.