316. Remove Duplicate Letters

316

MediumMonotonic Stack and Monotonic QueueMonotonic (greedy) stack with last-occurrence lookupLexicographically smallest subsequence with each letter once

Remove Duplicate Letters

Given a string s, remove duplicate letters so that every letter appears exactly once, and return the smallest result in lexicographical order among all such possible strings.

Open official problem prompt ↗

In plain English

Produce the alphabetically smallest string that still contains every distinct letter of the input exactly once, keeping original order.

Picture it like this

You are packing one of each souvenir type into a line on a shelf. If a nicer arrangement is possible because you will pass another copy of a bulky item later, you set the bulky one back now and grab it again when it fits better.

Example

Input: s = "cbacdcbc"
Output: "acdb"
Why: Every distinct letter (a, b, c, d) appears once, and 'acdb' is lexicographically smaller than any other one-of-each arrangement obtainable by deletion.

Constraints

1 <= s.length <= 10^4s consists of lowercase English letters

Pattern lesson

See the pattern, then code

Lexicographically smallest subsequence with each letter once

↗

Monotonic Stack and Monotonic Queue

Next greater or smaller value, nearest boundary, histogram, or window extremum.. Scan left to right building a result stack. If the current letter is smaller than the top of the stack and that top letter appears again later, popping it can only make the answer smaller, so pop it; otherwise keep it. Skip letters already placed.

New words, made simpleKnow these before the algorithm

Lexicographical order: Dictionary order: compare character by character, so 'acdb' < 'acdb'... wait it is the standard letter-by-letter comparison where earlier smaller letters win.
Last-occurrence map: For each letter, the final index where it appears, telling us whether it is safe to pop now because it recurs later.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Try all deletions

Combinatorially explosive and impossible for length 10^4.

Generate every one-of-each subsequence and pick the smallest.

Time ExponentialSpace Exponential

Best choiceGreedy monotonic stack

Single pass, provably optimal, only 26 possible letters.

Build the answer while popping a larger earlier letter whenever a smaller one comes and the larger recurs later.

Time O(n)Space O(1)

The rule we keep true

Invariant

The stack always holds distinct letters in the current best (increasing where possible) order, and any letter we pop is guaranteed to appear again later so nothing is lost.

Why this is correct

Reasoning

Popping a top letter t in favor of a smaller current letter c strictly improves lexicographical order at that position, and is only allowed when t occurs later, so we can still include t afterward. We never pop a letter that has no future copy, so all distinct letters survive; greedily improving each earliest position yields the global minimum.

The algorithm in three movesSay these aloud before coding

1Record the last index at which each letter occurs

at 'a' (i=2) pop b then c (both reappear) -> stack = [a]

2Scan the string; skip any letter already in the result

push c, d -> stack = [a, c, d]

3While the current letter is smaller than the stack top AND that top appears later, pop the top

final 'b' cannot pop d (last d = 4 < 6) -> [a, c, d, b]

4Push the current letter and mark it as present

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

1 · Readc=a, i=2

2 · AskCan we pop the top to go smaller?

3 · Update statestack = [c, b]

4 · Resultb (last 6>2) and c (last 7>2) both pop; stack = [a].

Key takeaway

The 'a' at index 2 evicts the earlier b and c because both recur later, seeding the smallest prefix.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 3Precompute last positions
Knowing each letter's final index tells us whether popping it now is safe because a later copy remains.
2
Lines 7-8Skip duplicates
A letter already on the stack must not be added twice; the each-letter-once rule forbids it.
3
Lines 9-10Greedy eviction
Pop a larger top only when a smaller current letter arrives AND the top reappears later, guaranteeing a smaller yet still-complete result.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

A string with all distinct letters returns itself unchanged
A string of one repeated letter returns that single letter
Already sorted distinct input needs no pops

Common beginner mistakes

Popping a letter that does NOT occur later, permanently losing it from the answer
Forgetting the seen set and inserting a letter twice
Using last-occurrence incorrectly with >= instead of >, mishandling the case where the top is the current index

Check your understanding

Why is the space complexity O(1) rather than O(n)?

Remove Duplicate Letters

Remove Duplicate Letters

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Monotonic Stack and Monotonic Queue