1081. Smallest Subsequence of Distinct Characters

String
Stack
Greedy
Monotonic Stack
Hash Table

TIME

O(n)

SPACE

O(26)

Intuition

We must keep exactly one copy of each distinct character, and want the result as small as possible lexicographically. Scanning left to right, a character already placed should be dropped in favour of a smaller one if we can safely re-add it later, i.e. if it occurs again further right. That "pop while the top is bigger and reappears later" rule is exactly a monotonic stack.

Approach

Record last[c] = the last index where character c appears.
Maintain a stack (the answer being built) and an inStack set.
For each index i with character c:
- If c is already in the stack, skip it (each character appears once).
- Otherwise, while the stack is non-empty, its top is greater than c, and that top's last occurrence is after i (so we can re-add it later), pop the top and remove it from inStack.
- Push c and mark it in inStack.
Join the stack into the result string.

The two pop conditions matter equally: top > c makes the result smaller, and last[top] > i guarantees we don't lose a character permanently.

Complexity

Time: O(n), each character is pushed and popped at most once
Space: O(26) = O(1), stack and set hold distinct lowercase letters only

Edge Cases

All distinct characters already ascending ("abc") → nothing pops, output unchanged
All same character ("aaaa") → one a
Popping must stop at the last occurrence: "cbacdcbc" keeps the final b (its earlier copies were poppable, the last one is not)
Single character → itself

Code

class Solution:
    def smallestSubsequence(self, s: str) -> str:
        """
        1081. Smallest Subsequence of Distinct Characters
        Time: O(n)
        Space: O(26)
        """
        last = {c: i for i, c in enumerate(s)}  # last occurrence of each char
        stack = []
        in_stack = set()

        for i, c in enumerate(s):
            if c in in_stack:
                continue
            # drop bigger characters that we can still re-add later
            while stack and stack[-1] > c and last[stack[-1]] > i:
                in_stack.remove(stack.pop())
            stack.append(c)
            in_stack.add(c)

        return "".join(stack)

/**
 * 1081. Smallest Subsequence of Distinct Characters
 * Time: O(n)
 * Space: O(26)
 */
class Solution {
    public String smallestSubsequence(String s) {
        int[] last = new int[26]; // last occurrence of each char
        for (int i = 0; i < s.length(); i++) {
            last[s.charAt(i) - 'a'] = i;
        }

        StringBuilder stack = new StringBuilder();
        boolean[] inStack = new boolean[26];

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (inStack[c - 'a']) {
                continue;
            }
            // drop bigger characters that we can still re-add later
            while (stack.length() > 0) {
                char top = stack.charAt(stack.length() - 1);
                if (top > c && last[top - 'a'] > i) {
                    stack.deleteCharAt(stack.length() - 1);
                    inStack[top - 'a'] = false;
                } else {
                    break;
                }
            }
            stack.append(c);
            inStack[c - 'a'] = true;
        }

        return stack.toString();
    }
}