Greedy Remove Stack

When To Use

Use this when building a lexicographically smallest/largest subsequence while you are allowed to drop elements.

Template

for x in sequence:
    while stack not empty and stack.top is worse than x and can_drop(stack.top):
        pop
 
    if should_take(x):
        push x
 
trim if needed

The hard part is usually can_drop.

Problems

Remove Duplicate Letters

Problem: smallest lexicographic subsequence containing each distinct char once.

Pattern: pop larger chars only if they appear again later.

Applied pseudocode:

freq = counts of chars
in_stack = empty set
 
for c in s:
    freq[c]--
 
    if c in in_stack:
        continue
 
    while stack not empty and stack.back > c and freq[stack.back] > 0:
        remove stack.back from in_stack
        stack.pop_back()
 
    stack.push_back(c)
    add c to in_stack

Remove K Digits

Problem: remove exactly k digits to make the smallest number.

Pattern: pop larger previous digits while drops remain.

Most Competitive Subsequence

Problem: lexicographically smallest subsequence of length k.

Pattern: pop larger previous elements while enough elements remain.

Create Maximum Number

Problem: create the largest length-k number from two arrays.

Pattern: best subsequence by greedy stack, then lexicographic merge.

Smallest Subsequence With Required Letter Repetition

Problem: smallest length-k subsequence with at least repetition copies of a given letter.

Pattern: greedy stack with separate drop budgets.