Smallest Subsequence With Each Letter Once

Pattern: Monotonic Stack · Difficulty: Hard · Asked at: Google, Amazon, ByteDance

Classic version: LeetCode 316 · LeetCode 402

Problem

Remove duplicate letters from s so every distinct letter appears exactly once, and the result is the lexicographically smallest among all such subsequences (relative order from s must be preserved).

Examples

smallest_unique_subsequence("bcabc")    → "abc"
smallest_unique_subsequence("cbacdcbc") → "acdb"

Starter code

def smallest_unique_subsequence(s: str) -> str:
    pass

Hints

Where this shows up in data engineering

Greedy-with-lookahead on a stack is the shape of “produce the smallest/cheapest valid sequence while preserving order”, e.g. choosing which duplicate events to keep so the output is canonical and minimal. It’s also a strong signal problem: you must prove why popping is safe.

Solution

def smallest_unique_subsequence(s: str) -> str:
    last = {c: i for i, c in enumerate(s)}
    stack, in_stack = [], set()
    for i, c in enumerate(s):
        if c in in_stack:
            continue
        # a bigger letter on top can go if it appears again later
        while stack and stack[-1] > c and last[stack[-1]] > i:
            in_stack.discard(stack.pop())
        stack.append(c)
        in_stack.add(c)
    return "".join(stack)

Tests

Your solution should pass these:

assert smallest_unique_subsequence("bcabc") == "abc"
assert smallest_unique_subsequence("cbacdcbc") == "acdb"
assert smallest_unique_subsequence("a") == "a"
assert smallest_unique_subsequence("abacb") == "abc"
assert smallest_unique_subsequence("ecbacba") == "eacb"

Explanation

Greedy argument: if the stack top t is greater than c and t appears later, placing c before t gives a smaller string and loses nothing (we can still place t later). If t never appears again, it must stay.

Skipping letters already placed is safe: the earlier placement is at least as good since everything after it is still free to be arranged.

Complexity: O(n) time (each letter pushed/popped at most once), O(alphabet) space.

Follow-up questions