Greedy: Given a number and a value k, return the smallest digit after removing k digits

Problem Statement:

Given a number and a value k, return the smallest digit after removing k digits

Example:

Input: num = "12345" k = 3

Output:

Solution Explanation:

We will use greedy approach to solve the problem.

Greedy approach is suitable because, we need the smallest resulting number and at each step we make locally optimal choice.

We will use stack to solve the problem.

Take a stack and traverse the string and compare with the top of the stack.

If the current digit is smaller than the top of the stack and k > 0, then pop from the stack till a suitable position for the current digit is found.

Time Complexity: O(1)
Space Complexity: O(1)

Code Solution

#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;


string solution(string num, int k) 
{
    stack<char> stack;
    
    for (char digit : num) 
    {
        while (!stack.empty() && k > 0 && stack.top() > digit)
         {
            stack.pop();
            k--;
        }
        stack.push(digit);
    }

	//if k is non zero, remove the remaining elements from stack    
    while (k > 0 && !stack.empty()) 
    {
        stack.pop();
        k--;
    }
    
    string result;
    while (!stack.empty()) 
    {
        result += stack.top();
        stack.pop();
    }

    reverse(result.begin(), result.end());

    size_t pos = result.find_first_not_of('0');
    result = (pos == string::npos) ? "0" : result.substr(pos);
    
    return result;
}


int main() 
{
    string str = "12345";
    int k = 3;

    cout <<solution(str, k);
}

Output

12