Problem Overview

You are given a string num that represents a non-negative integer, and an integer k.
Your task is to remove exactly k digits from the number so that the resulting number is as small as possible.
The final result cannot contain leading zeros. If all digits are removed, return "0".

Key Idea

This is a classic problem where a greedy algorithm with a stack leads to the optimal result.

To get the smallest possible number, whenever you see a digit that is smaller than the previous digit, you should remove the previous digit.
This is because a smaller digit earlier in the number makes the entire number smaller.

Example:
Choose "1219" instead of "1432219" by removing digits that break the increasing pattern.

Step-by-Step Explanation

1. Use a Stack (string used as a stack)

We iterate over each digit in num.
For every digit c:

• While the stack is not empty

• AND we still have digits to remove (k > 0)

• AND the last digit in the stack is greater than c

we remove the last digit from the stack.
This ensures we maintain the smallest possible sequence.

After removing necessary digits, we push c into the stack.

2. If k still remains

If we finish the loop and k > 0, it means the digits were already non-decreasing.
In this case, we remove digits from the end, because removing bigger digits later still reduces the number.

3. Remove Leading Zeros

The result might contain leading zeros, for example:

• "10200" → after removing '1' → "0200"
  We must remove all leading zeros.

If the result becomes empty, return "0".

Example Walkthrough

Input:

num = "1432219", k = 3

Process

• Compare digits and remove larger ones when possible

• Maintain the smallest possible pattern

Stack transitions:

1  
14  
143  
1432 → 3 < 2? remove 2  
14 32 → 3 < 3? equal, keep  
14322 → 1 remaining removal  
143221 → remove 2 → remove second 2 → remove 3  
Final stack: 1219

Output:

"1219"

Time and Space Complexity

• Time Complexity: O(n), where n = number length
  Each digit is pushed and popped at most once

• Space Complexity: O(n) for the stack

Final Code

class Solution {
public:
    string removeKdigits(string num, int k) {
        string st; 
        
        for (char c : num) {
            while (!st.empty() && k > 0 && st.back() > c) {
                st.pop_back();
                k--;
            }
            st.push_back(c);
        }
        
        while (k > 0 && !st.empty()) {
            st.pop_back();
            k--;
        }
        
        int i = 0;
        while (i < st.size() && st[i] == '0') i++;
        
        string res = st.substr(i);
        if (res == "") return "0";
        return res;
    }
};