I've been working through coding problems that I can understand when reading solutions but struggle to solve on my own. This series is about breaking down the "why does this actually work" part. Not tutorials. Just honest breakdowns of where my thinking got stuck and what finally unstuck it.
The problem that looked familiar
LeetCode 316: Remove Duplicate Letters. Given a string like "cbacdcbc", remove duplicate characters so every letter appears exactly once, and the result is the smallest possible in lexicographical order. The answer here is "acdb".
I'd just finished learning monotonic stacks for Sum of Subarray Minimums. Greedy popping, maintaining order, comparing against the stack top. I recognized the pattern immediately: scan the string, and if the current character is smaller than what's on the stack and the stack-top character appears later in the string, pop it. Classic monotonic stack.
So I coded it up, and it was wrong.
Where I got stuck
My first solution treated uniqueness as a cleanup step. I let duplicates pile up in the stack, then deduplicated at the end by reading from the bottom and skipping repeats. The stack logic would handle ordering, and the dedup pass would handle uniqueness. Two separate concerns, handled separately.
That's the thinking that broke it. In this problem, ordering and uniqueness aren't separate. They're coupled. The greedy decisions the stack makes (should I pop this character or keep it?) depend on knowing exactly which characters are already committed to the result. A duplicate sitting in the stack corrupts those decisions.
Duplicates poison the greedy logic
Here's the specific failure. Take "abacb".
With post-hoc deduplication, my stack processed it like this:
| Step | Char | Stack action | Stack |
|---|---|---|---|
| 1 | a | push | [a] |
| 2 | b | a < b, push | [a, b] |
| 3 | a | b > a, pop b. a = a, push | [a, a] |
| 4 | c | a < c, push | [a, a, c] |
| 5 | b | c > b but c has freq 1, push | [a, a, c, b] |
Dedup from the left: "acb".
The correct answer is "abc" (a at index 0, b at index 1, c at index 3).
What went wrong? Step 3 pushed a second a into the stack. That second a caused b to get popped unnecessarily. With b gone, it could only re-enter at the end, after c. The duplicate a sitting in the stack made the greedy logic produce a worse ordering.
If I'd skipped the second a entirely (it's already in the result, no need to process it), b would have stayed in the stack, and the final answer would have been "abc".
The seen-set: a co-pilot for the stack
The fix is a set that tracks what's currently in the stack. Before doing any work for a character, check the set. If the character is already there, skip it. Decrement its frequency (you've consumed this occurrence) and move on.
in_stack = set()
for char in s:
freq[char] -= 1 # this occurrence is consumed
if char in in_stack: # already in the result
continue
# ... stack logic ...
stack.append(char)
in_stack.add(char)
This isn't just a performance optimization. It fundamentally changes what the stack sees. Without it, the stack is making ordering decisions with ghost characters that shouldn't be there.
Popping means evicting, and the set needs to know
Here's the second thing that got me. I added the set, but when I popped a character from the stack, I forgot to remove it from the set.
Think about what popping means in this problem. You're looking at the stack-top character and saying: "You're bigger than what I've got now, and you appear again later in the string. I'll use a later copy of you instead." That character is leaving your result. It's no longer committed. So when you encounter it again later, it needs to be allowed back in.
If the set still thinks it's in the stack, the later occurrence gets skipped. The character ends up nowhere.
Trace "cbacdcbc" with a stale set:
| Step | Char | Action | Stack | Set |
|---|---|---|---|---|
| 1 | c | push | [c] | {c} |
| 2 | b | pop c (freq 3>1), push b | [b] | {c, b} |
| 3 | a | pop b (freq 2>1), push a | [a] | {c, b, a} |
| 4 | c | skipped (set says c is here) | [a] | {c, b, a} |
| 5 | d | push | [a, d] | {c, b, a, d} |
| 6-8 | c,b,c | all skipped | [a, d] | {c, b, a, d} |
Result: "ad". The actual answer is "acdb".
Characters c and b were popped from the stack but never removed from the set. Every future occurrence got skipped. They vanished from the result entirely.
The fix: when popping, remove from the set before (or during) the pop.
while stack and stack[-1] > char and freq[stack[-1]] > 0:
in_stack.remove(stack[-1])
stack.pop()
The complete solution
class Solution:
def removeDuplicateLetters(self, s: str) -> str:
freq = {}
for c in s:
freq[c] = freq.get(c, 0) + 1
stack = []
in_stack = set()
for c in s:
freq[c] -= 1
if c in in_stack:
continue
while stack and stack[-1] > c and freq[stack[-1]] > 0:
in_stack.remove(stack[-1])
stack.pop()
stack.append(c)
in_stack.add(c)
return ''.join(stack)
Three things work together: the stack maintains lexicographic order, the frequency map answers "is it safe to evict this character?", and the set tracks what's currently committed. Remove any one piece and the solution breaks.
The pattern underneath
Standard monotonic stack problems (next greater element, daily temperatures, histogram) only care about ordering. Every element eventually enters the stack exactly once. The stack just controls when elements leave and what order they end up in.
Remove Duplicate Letters adds a constraint: each character can appear in the result at most once. That single constraint means the stack can't operate alone anymore. It needs a partner that tracks membership, and that partner has to stay perfectly in sync. Every push updates the set. Every pop updates the set. If they drift, the greedy logic makes decisions based on a state that doesn't match reality.
This "stack + membership set" pattern shows up in a few other places. Anytime a monotonic stack problem adds a uniqueness or "already used" constraint, look for it.
What to practice next
These are ordered roughly by how they connect to the ideas above.
- LC 1081, Smallest Subsequence of Distinct Characters (medium). Literally the same problem with a different name. Good for confirming you actually get it and didn't just memorize the solution for 316.
- LC 402, Remove K Digits (medium). Monotonic stack with a removal budget instead of a uniqueness constraint. Tests whether you understand the greedy popping logic on its own.
- LC 321, Create Maximum Number (hard). Combines monotonic stack selection from two arrays. The merging step is tricky.
- LC 907, Sum of Subarray Minimums (medium). Classic monotonic stack without the uniqueness layer. If you haven't done this one, it's the best way to solidify the base pattern.
- LC 84, Largest Rectangle in Histogram (hard). Another pure monotonic stack problem. Boundary finding in both directions.
I'm building Levelop to help people get better at problems like these. If you want more breakdowns like this, check it out.
Top comments (0)