Smallest Subsequence of Distinct Characters — LeetCode Daily Python Solution (the greedy stack trick nobody sees)

Introduction

Every so often you run into a LeetCode problem that looks like a sorting exercise on the surface but is actually testing something deeper: whether you can reason about safety. "Smallest Subsequence of Distinct Characters" (also known as LeetCode 316, "Remove Duplicate Letters") is exactly that kind of problem, and it shows up regularly in interviews at companies like Google and Amazon — not because the code is long, but because the greedy insight is easy to get almost right and subtly wrong.

The reason this problem is worth your time goes beyond passing an interview. The same greedy-stack-with-lookahead pattern shows up in real systems: log compaction, deduplication pipelines, and text-normalization tools all lean on this idea of "keep the smallest useful thing now, but only if you're not burning a bridge you'll need later." Learn the pattern once here, and you'll start recognizing it in places that have nothing to do with LeetCode.

Problem Overview

You're given a string made of lowercase letters. Your job is to produce the smallest possible string (in dictionary order) that:

1. Contains every distinct character from the original string exactly once.
2. Preserves the relative order those characters appeared in the original string — in other words, your answer must be a subsequence of the input.

So you're not free to rearrange letters however you like. You can only pick which occurrences to keep and which to drop, and the leftover letters must stay in their original left-to-right order.

For example, given bcabc, the distinct letters are b, c, and a. There are multiple subsequences that contain all three exactly once, but the smallest one alphabetically is abc.

Example

Input: "bcabc" Output: "abc"

Why? The distinct letters are a, b, c. Several subsequences satisfy "each letter once, order preserved" — for instance bca, bac, abc — but only abc is the alphabetically smallest one that's still a valid subsequence of the original string.

Input: "cbacdcbc" Output: "acdb"

This one's trickier. Let's trace the intuition: a and b are easy picks. c shows up early but gets pushed out because a smaller letter (a) comes later and c itself reappears further down the string, so dropping the early c doesn't cost us anything. d has nothing smaller after it, so it stays put once added. b closes out the string. The result: acdb.

Intuition

Here's how an experienced engineer would approach this without knowing the "official" solution.

First instinct: this smells like sorting. You want the smallest possible letters as early as possible. But you can't just sort the distinct letters — that would break the subsequence constraint. If b appears before a in the original string but a never appears again after that point, you're not allowed to put a before b in your answer, because there's no valid subsequence that does that.

So the real question becomes: when is it safe to prefer a smaller letter over one you've already committed to?

Think of building your answer as a stack, one letter at a time, left to right. At each step you have two choices for the current letter:

• If you haven't used this letter yet, you want it in your answer.
• Before adding it, check whether the letter currently on top of your stack is bigger than it. If it is, you'd love to remove that top letter and let the smaller one take its place earlier in the answer.

But you can only do that removal if the bigger letter you're kicking out is not gone for good — meaning it needs to appear again later in the string so you can add it back afterward. This is the one insight that makes the whole algorithm safe: never discard a letter you can't get back.

That single lookahead check — "does this letter reappear later?" — is what separates a correct greedy algorithm from a broken one.

Brute Force Solution

Idea: Generate candidate orderings of the distinct letters (or greedily try to build the lexicographically smallest string character by character by trial), and check whether each candidate is actually a valid subsequence of the original string. Keep the smallest one that works.

Algorithm:

1. Find the set of distinct characters.
2. Try building strings in increasing lexicographic order (or permute the letters).
3. For each candidate, verify it's a valid subsequence of the input string.
4. Return the first valid one.

Advantages:

• Conceptually simple to explain in an interview — it directly restates the problem.
• Easy to verify correctness on small inputs.

Disadvantages:

• The number of orderings to check grows combinatorially with the number of distinct letters (up to 26! in the worst case, though pruning helps).
• Subsequence-checking itself costs O(n) per candidate, so total work explodes fast.
• Impractical the moment the input gets even moderately long.

Time complexity: Exponential in the number of distinct characters (roughly O(k! · n) in the naive version). Space complexity: O(k) to O(k!) depending on how candidates are generated.

This is worth mentioning out loud in an interview to show you understand the goal, but you should pivot to the stack approach immediately afterward.

Optimal Solution

The optimal approach uses two supporting tools and one greedy stack:

Tool	Purpose
Last-occurrence map	For each letter, store the last index it appears at in the string.
seen set	Track which letters are already placed in our stack, so we never add duplicates.
Stack	Build the answer incrementally; only the top can be added or removed.

Step 1 — Build the last-occurrence map. Scan the string once and record, for every character, the last index at which it appears. This is what lets us later ask "if I remove this letter now, can I still get it back?"

Step 2 — Walk the string, skipping already-placed letters. If a letter is already in our seen set, skip it entirely — we only ever want one copy in the final answer.

Step 3 — The kick-out condition. Before pushing the current letter, look at the top of the stack. While all three of these are true:

• the stack isn't empty,
• the top of the stack is alphabetically greater than the current letter,
• the top of the stack still appears again later (its last-occurrence index is greater than the current position),

...pop the top off the stack and mark it as no longer seen (since we'll add it back later).

Step 4 — Push and continue. Once the popping stops (either the stack is empty, the top is smaller, or the top won't reappear), push the current letter and mark it seen. Repeat for the rest of the string.

At the end, the stack is the answer — just join it into a string.

Here's a small trace to visualize the "kick-out":

String: b c a b c
Index:  0 1 2 3 4

i=0 'b': stack=[b]              seen={b}
i=1 'c': stack=[b,c]            seen={b,c}
i=2 'a': top 'c' > 'a' and 'c' reappears at i=4 → pop 'c'
         top 'b' > 'a' and 'b' reappears at i=3 → pop 'b'
         stack=[a]              seen={a}
i=3 'b': stack=[a,b]            seen={a,b}
i=4 'c': stack=[a,b,c]          seen={a,b,c}

Answer: "abc"

Python Code

def smallest_subsequence(s: str) -> str:
    """Return the smallest subsequence of s containing each distinct
    character exactly once, using a greedy monotonic stack."""

    last_occurrence = {char: idx for idx, char in enumerate(s)}
    stack = []
    seen = set()

    for idx, char in enumerate(s):
        if char in seen:
            continue

        # Kick out a bigger letter only if it reappears later.
        while stack and stack[-1] > char and last_occurrence[stack[-1]] > idx:
            seen.remove(stack.pop())

        stack.append(char)
        seen.add(char)

    return "".join(stack)


def demo():
    assert smallest_subsequence("bcabc") == "abc"
    assert smallest_subsequence("cbacdcbc") == "acdb"
    assert smallest_subsequence("") == ""
    assert smallest_subsequence("a") == "a"
    assert smallest_subsequence("edcba") == "edcba"
    print("All checks passed.")


if __name__ == "__main__":
    demo()

Code Walkthrough

• last_occurrence = {char: idx for idx, char in enumerate(s)} builds the lookup table in one pass — since we overwrite as we go, each letter ends up mapped to its last index.
• stack holds our answer-in-progress; seen tracks membership so we never push a duplicate.
• if char in seen: continue skips any letter we've already placed — we only want one copy of each.
• The while loop is the core logic: it only pops when the top is strictly larger than the current character and that top letter has a future occurrence to fall back on (last_occurrence[stack[-1]] > idx). If the top letter has no later appearance, the loop stops immediately, protecting it from being lost.
• seen.remove(stack.pop()) pops and un-marks the letter in one step, since it may get pushed again later.
• After the loop, we push the current character and mark it seen.
• "".join(stack) converts the final stack into the answer string.

Dry Run

Let's trace "cbacdcbc" fully.

i	char	last_occurrence	Action	Stack after
0	c	c:6	push c	[c]
1	b	b:6	b < c? no (b<c actually — wait check condition: top='c' > 'b' and last[c]=6>1 → pop c; push b	[b]
2	a	a:2	top='b' > 'a', last[b]=6>2 → pop b; stack empty → push a	[a]
3	c	c:6	c not seen, top='a' < 'c' → no pop; push c	[a,c]
4	d	d:4	top='c' < 'd' → no pop; push d	[a,c,d]
5	c	—	already seen → skip	[a,c,d]
6	b	b:6	top='d' > 'b' but last[d]=4, not >6 → stop; push b	[a,c,d,b]
7	c	—	already seen → skip	[a,c,d,b]

Final stack: a, c, d, b → "acdb", matching the expected answer.

Complexity Analysis

Time: O(n), where n is the length of the string. Building the last-occurrence map is one O(n) pass. In the main loop, each character is pushed onto the stack at most once and popped at most once — so even though the while loop looks like it could be expensive, the total number of push/pop operations across the entire run is bounded by O(n), giving amortized O(1) work per character.

Space: O(26) in the worst case, since the alphabet is fixed (lowercase English letters). The stack, the seen set, and the map all scale with the number of distinct characters, not the length of the string — effectively constant space.

This is what makes the stack approach fundamentally better than brute force: brute force complexity grows with the number of orderings (factorial-ish), while the stack approach grows linearly with the length of the input, no matter how it's structured.

Alternative Solutions

Besides the brute-force sorting/permutation approach discussed earlier, there isn't a meaningfully different efficient algorithm — the greedy stack is the standard optimal solution for this problem. Some implementations use a fixed-size array of 26 booleans instead of a Python set for seen, and a 26-element array instead of a dict for last_occurrence. This shaves a small constant factor off runtime since array indexing is faster than hashing, but the algorithmic idea is identical.

Edge Cases

• Empty string: Returns "" immediately — the loop never executes.
• Single character: Returns that character unchanged.
• All characters already unique (e.g., "abcdef"): The while loop never fires since nothing needs kicking out; the stack builds straight through in the original order.
• Already sorted, strictly decreasing (e.g., "edcba"): Looks like it should collapse, but since no letter reappears later, the last-occurrence check blocks every pop — the answer is the string unchanged.
• Repeated letters clustered together (e.g., "aaabbbccc"): Only the first occurrence of each letter matters; everything else gets skipped via the seen check.

Common Mistakes

1. Forgetting the last-occurrence check before popping — this is the single most common bug, and it's exactly the mistake called out in the video. Without it, you might discard a letter that never appears again, making the final "subsequence" invalid.
2. Popping a letter but forgetting to remove it from seen — if you don't un-mark it, the algorithm will refuse to re-add it later, producing a string missing a required letter.
3. Comparing characters incorrectly (e.g., using >= instead of > in the pop condition) — this can pop letters unnecessarily or fail to pop when it should.
4. Not skipping already-seen letters, which lets duplicates leak into the stack and break the "each letter exactly once" requirement.
5. Using the first occurrence instead of the last when building the lookup map — this silently breaks the safety check, since you'd think a letter is "gone" when it actually reappears later.

Interview Questions

• What happens if the input contains uppercase letters or digits — how would you adapt the solution?
• Can you prove that the greedy choice (popping when safe) always leads to a globally optimal answer?
• How would you modify this to return the lexicographically largest valid subsequence instead?
• What's the maximum number of push/pop operations possible, and why does that bound the time complexity?
• How does this problem relate to other monotonic stack problems you've seen?

Similar Problems

• LeetCode 316 – Remove Duplicate Letters: This is effectively the same problem under a different name; the exact same solution applies.
• LeetCode 402 – Remove K Digits: Uses a nearly identical greedy monotonic stack pattern to remove digits and minimize the resulting number.
• LeetCode 496 – Next Greater Element I: Builds foundational monotonic stack intuition, even though the goal is different.
• LeetCode 84 – Largest Rectangle in Histogram: A harder monotonic stack problem that uses the same "pop while condition holds" structure.

Key Takeaways

The core lesson here isn't really about strings — it's about recognizing when a greedy choice is safe. Whenever you're tempted to make a locally better choice (a smaller letter, a smaller digit, a shorter path), ask yourself: "if I make this choice now, am I permanently losing something I'll need later?" A last-occurrence or lookahead map is often the tool that turns an unsafe greedy idea into a provably correct one. Once this pattern clicks, you'll start spotting it in a whole family of stack-based greedy problems.

Watch the Video

If you want to see this traced live on the whiteboard, including the exact moment where letters get popped and why, check out the full walkthrough here: {LINK}

About the Series

This breakdown is part of the Daily Python LeetCode series, where each problem gets the same treatment: build the intuition first, then the code, so you actually understand why a solution works instead of memorizing it. If you're prepping for interviews or just want to get sharper at recognizing algorithmic patterns, this series is built to get you there one problem at a time.

Call To Action

If this breakdown helped the trick click, subscribe on YouTube for the daily walkthroughs, and subscribe to the Substack for the written version delivered straight to your inbox. Drop a comment with the string you'd want traced next, and share this with a friend who's grinding LeetCode right now — it genuinely helps a small channel grow.

---

    stack = []
    seen = set()
    for i, c in enumerate(s):
        if c in seen:
            continue