Greedy with Monotonic Stacks

Removing exactly K digits while preserving the relative order of the others asks for a smallest subsequence of a fixed length. Earlier digits dominate lexicographic comparison, so a smaller incoming digit can justify deleting larger preceding digits. A monotonic stack implements these safe exchanges in linear time. Leading-zero formatting is separated from the actual K-deletion optimization.

Prerequisites: Stacks; lexicographic order; amortized analysis. Related existing lessons: Monotonic Stacks.

Build the idea

1. Define the candidate order

   Every retained digit must appear in the original order, and exactly n−K digits survive. For equal-length digit strings, lexicographic and numeric order agree even with leading zeros. The primary raw result therefore preserves zeros. A second output strips leading zeros for conventional number display, using 0 when every remaining digit is zero or all digits were removed.

2. Pop a larger predecessor

   Scan left to right. While deletions remain and stack.back()>current, pop that larger earlier digit and spend one deletion. Append current afterward. The retained candidate prefix is as small as possible under the budget used so far. Equal digits are not popped: doing so yields no earlier improvement and may waste a deletion needed later.

   $$\mathrm{retainedLength}=n-K$$

3. Correctness proof: improve the earliest difference

   If a larger retained predecessor immediately before a smaller next digit can be deleted, keeping it makes the earliest differing retained position larger than a completion that removes it. Spending a deletion there is therefore safe before spending it on any later less-significant digit. Repeated pops expose earlier improvements as needed. If deletions remain after the scan, the candidate is nondecreasing, so deleting from the end preserves the smallest possible prefix. Together these exchanges produce the smallest length n−K subsequence.

4. Trace the sample

   For 1432219 with K=3, append 1,4. Incoming 3 removes 4, leaving 13 with two deletions. Incoming 2 removes 3, leaving 12 with one deletion. Append another 2. Incoming 1 removes the last 2, exhausting the budget; append 1 and finally 9, giving 1219. The algorithm cannot now remove the earlier 2 because exactly three deletions were available.

5. Explain amortized processing

   A digit enters the string stack once and is popped at most once, so the nested while loops are linear overall. The final suffix deletion is also bounded by n. Do not sort the digits: that would change their relative order and solve a different problem. Empty raw output is explicitly labeled EMPTY, while its formatted numeric display is 0.

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<string>
int main(){
    std::string digits;
    int k;
    std::cin>>digits>>k;
    std::string stack;
    for(char c:digits){
        while(k>0&&!stack.empty()&&stack.back()>c){
            stack.pop_back();
            --k;
        }
        stack+=c;
    }
    while(k>0){
        stack.pop_back();
        --k;
    } // If no earlier improvement is possible, delete from the least significant end.
    std::cout<<(stack.empty()?"EMPTY":stack)<<'\n';
    auto first=stack.find_first_not_of('0');
    std::cout<<(first==std::string::npos?"0":stack.substr(first))<<'\n';
}

Complexity analysis

O(n) time by one push/pop per digit and O(n) stack/output space. The numeric value is never parsed, so arbitrarily many digits within the length bound do not cause integer overflow.

Example input and output

Read a nonempty digit string (length≤100000) and K with 0≤K≤length. Print the smallest raw subsequence after exactly K deletions (EMPTY if none), then its leading-zero-normalized number (0 if empty/all zeros).

Input

1432219 3

Output

1219
1219

Greedy removes 4,3 and one of the two consecutive 2 digits before the smaller 1.

Practical applications

Use monotonic stacks to discard dominated earlier candidates when an earlier improvement outranks every later one. Next-greater-element stacks use similar mechanics but answer a different question and need their own invariant, not this lexical-optimality proof.

Check your understanding

Where should leftover deletions be spent after processing a nondecreasing candidate?

Put it into practice

Enumerate all length n−K subsequences for short digit strings.