Pattern Guide
Greedy String Problems
"Remove k digits, largest number, reorganize string. Monotone stack for ordering."
Greedy string problems construct optimal strings by local decisions. Key patterns: remove k digits to minimize result (monotone stack), arrange numbers to form largest concatenation (custom comparator), reorganize string so no two adjacent chars are same (greedy with max-heap), remove duplicate letters (stack with seen tracking), and create lexicographically smallest/largest string under constraints.
Problems you can solve with this pattern
4 problems · click any to start solving
// Remove k digits to make smallest number
function removeKDigits(num, k) {
const stack = [];
for (const c of num) {
while (k > 0 && stack.length && stack[stack.length-1] > c) {
stack.pop(); k--;
}
stack.push(c);
}
// Remove remaining k digits from end
while (k-- > 0) stack.pop();
// Remove leading zeros
const result = stack.join('').replace(/^0+/, '');
return result || '0';
}
// Largest number from array of integers
function largestNumber(nums) {
const strs = nums.map(String);
strs.sort((a, b) => (b + a).localeCompare(a + b));
const result = strs.join('');
return result[0] === '0' ? '0' : result;
}Remove k digits: use monotone increasing stack. When current digit < stack top and k > 0, pop (that's a removal). After processing, if k remaining, remove from end (stack). Largest number: sort strings by comparing a+b vs b+a. Reorganize string: max-heap, alternate placing most frequent. Remove duplicate letters: maintain stack with seen set; pop stack when current char is smaller and more occurrences remain.
// Remove k digits to make smallest number
function removeKDigits(num, k) {
const stack = [];
for (const c of num) {
while (k > 0 && stack.length && stack[stack.length-1] > c) {
stack.pop(); k--;
}
stack.push(c);
}
// Remove remaining k digits from end
while (k-- > 0) stack.pop();
// Remove leading zeros
const result = stack.join('').replace(/^0+/, '');
return result || '0';
}
// Largest number from array of integers
function largestNumber(nums) {
const strs = nums.map(String);
strs.sort((a, b) => (b + a).localeCompare(a + b));
const result = strs.join('');
return result[0] === '0' ? '0' : result;
}- Smallest number after k removals: monotone increasing stack
- Largest concatenation: custom comparator a+b vs b+a
- No two adjacent same: max-heap interleaving (feasible if max_freq ≤ (n+1)/2)
- Lexicographically smallest subsequence (no dups): stack + can-pop-later check
Monotone stack greedy principle: Maintain invariant (increasing/decreasing) by popping violations when the budget (k removals, future occurrences) allows. The stack always represents the current best prefix.