Problem Statement

Given a string nums representing a non-negative integer, and an integer k, find the smallest possible integer after removing k digits from num.

Examples

Example 1:

Input: nums = "541892", k = 2
Output: "1892"

Explanation: Removing the first two digits 5 and 4 yields the smallest number, 1892.

Example 2:

Input: nums = "1002991", k = 3
Output: "21"

Explanation: Remove the first digits 1(leading one), 9, and 9 to form the new number 21 (The output must not contain the leading zeroes) which is the smallest.

Different Approaches

1️⃣ Monotonic Stack

Intuition:

To get the smallest possible integer, the smaller digits must be kept at the beginning. This can be achieved by getting rid of K larger digits using a simple greedy approach that works by processing each digit and keeping the smallest possible digit, aiming for the smallest resulting number. Prioritizing smaller digits for the leftmost positions ensures the resulting number is minimized.

To facilitate the greedy approach, a stack data structure can be used because:

• LIFO (Last In, First Out): The stack allows access to the most recently added element, useful when comparing and potentially removing the last chosen element to eliminate a larger digit.
• Order Preservation: The stack maintains the relative order of elements, crucial when the sequence of digits must be preserved.

Approach:

1. Use a stack to keep track of the digits of the resulting number. Iterate through each digit of the input string.
2. Remove the previous digits from the stack if they are larger than the current digit and the removal count (k) allows. This step ensures that the remaining digits form the smallest possible number.
3. If there are still digits left to be removed after the iteration, continue removing the digits from the end of the stack.
4. Collect the remaining digits from the stack and form the resulting number by reversing the digits.

Edge Cases:

• When K is equal to the size of the string:
  • In such cases, all the digits will be removed from the given numbers, thus "0" can be returned.
• When the resulting number contains leading zeroes:
  • In such cases, the leading zeroes must be removed before returning the resultant number.
• When there are still removals left:
  • Consider the example: nums = "1234" amd k = 2
    Here, there will be no removals performed, however, two removals can be performed. Thus, to utilize all the given removals, the last digits of the number can be removed before returning the result.

Code:

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    /* Function to find the smallest possible 
    integer after removing k digits */
    string removeKdigits(string nums, int k) {
        
        stack <char> st; // Stack
        
        // Traverse on the given string
        for(int i=0; i < nums.size(); i++) {
            
            // Current digit
            char digit = nums[i];
            
            /* Pop last digits (when possible)
            if a smaller digit is found*/
            while(!st.empty() && k > 0
                  && st.top() > digit) {

                st.pop(); // Pop the last digit
                k--; // Decrement K by 1
            }
            
            // Push the current digit
            st.push(digit);
        }
        
        // If more digits can be removed
        while(!st.empty() && k > 0) {
            
            st.pop(); // Pop the last added digits
            k--; // Decrement K by 1
        }
        
        // Handling edge case
        if(st.empty()) return "0";
        
        // To store the result
        string res = "";
        
        // Adding digits in stack to result
        while(!st.empty()) {
            res.push_back(st.top());
            st.pop();
        }
        
        // Trimming the zeroes at the back
        while(res.size() > 0 && 
              res.back() == '0') {

            res.pop_back();
        }
        
        // Reverse to get the actual number
        reverse(res.begin(), res.end());
        
        // Edge case
        if(res.empty()) return "0";
        
        // Return the stored result
        return res;
    }
};

int main() {
    string nums = "541892";
    int k = 2;
    
    /* Creating an instance of 
    Solution class */
    Solution sol; 
    
    /* Function call to find the smallest 
    possible integer after removing k digits */
    string ans = sol.removeKdigits(nums, k);
    
    cout << "The smallest possible integer after removing k digits is: " << ans;
    
    return 0;
}

Complexity Analysis:

• Time Complexity:O(N) (where N is the length of the given number)
  • Traversing the given string takes O(N) time.
  • Each element is pushed onto and popped from the stack at most once in worst-case taking o(N) time.
  • Removing the remaining digits (if k > 0) takes O(k) time which can go upto O(N) in worst-case.
  • Forming the result, trimming the zeros and reversing the digits takes O(N) time.
• Space Complexity:O(N)
  • The stack space can be O(N) in the worst-case.
  • The space required to store the result is O(N) in worst-case.