841. The Largest Number You Can Leave Behind

A number is given as a string of digits s, possibly with leading zeros. Delete exactly k of its digits so that the digits left behind, READ IN THEIR ORIGINAL ORDER, form the LARGEST possible number. Print that number with no leading zeros; print 0 if the result is zero.

1432219, k = 3 -> 4329 10200, k = 1 -> 1200 5337, k = 2 -> 57

For the first row, keeping four digits, the best choice is the 4, then the 3, then a 2, then the 9.

## The greedy rule, and why it is correct

Read the digits left to right and hold the answer so far on a stack. When digit c arrives, any digit already on the stack that is SMALLER than c is in the wrong place: deleting it moves a bigger digit one place further left, and in a number of fixed length, a bigger digit further left always wins, no matter what the remaining digits are.

while the stack is non-empty and the top is < c and deletions remain: pop, and use up one deletion push c

The exchange argument is the proof. Suppose the stack top is t and t < c. Compare the answer that keeps t with the answer that drops it. Both have the same length, both agree on every position before this one, and at this position the first has t and the second has c or something even better. Since c > t, the second is strictly larger. Deleting is never worse.

## Which direction the stack runs, and why

The stack is kept NON-INCREASING from the bottom up, because we want the big digits first. That is the opposite of problem 172, which minimises and therefore keeps its stack non-decreasing by popping whenever the top is LARGER than the arrival. The two problems are one character apart and the character is the comparison operator. It is worth writing them side by side once.

## The two things that are not the greedy rule

If deletions are still unused when the string runs out, the digits are already non-increasing, so the smallest digits are at the END. Drop the last k remaining. Dropping from the front instead is the classic wrong finish.

Leading zeros can only survive when the entire result is zeros, since a leading zero would have been popped by any later non-zero digit. Strip them, and print 0 if nothing is left after stripping. Test 0000 with k = 2.

## Why it is linear

Every digit is pushed once and popped at most once, and there are at most k pops in total because each one spends a deletion. The loop looks nested but costs O(n).

## Related problems

Problem 172 removes k digits to make the number as SMALL as possible, and problem 842 picks a subsequence of a fixed length rather than deleting a fixed count.

## Cost

Time O(n). Space O(n).

Constraints - `1 ≤ |s| ≤ 200000` - `0 ≤ k < |s|` - `s` contains digit characters only