Stack: Make digit minimum by removing k digits.

Problem Statement:

You are given a string represents a integer and integer k.
You need to remove k digits from the integer and it must be the smallest.

Example

Input: num = “1432219”, k = 3
Output: “1219”

Remove 4, 3, 2 to make the digit smallest.

Solution

We will use stack to solve the problem.
Initially push the first element into the stack.
From the next elemet check if it is smaller than the element present in the stack, then pop the element from the stack.

By making the current has the capaticy to make the digit smaller.

Example:
num = “1432219”, k = 3

Stack: 1

Then when we ecounter 4, it is not less than 1, so insert
Stack: 1 4

Next 3, we pop 4 and push 3. K = 2
Stack: 1 3

Next 2, pop 3, and push 2. K =1
Stack: 1 2

Next 2, and push 2.
Stack: 1 2 2

Next 1, and pop 2 push 1. K = 0.
Stack: 1 2 1

Insert all other leftout digit: 1219

Hence our result

Solution in C++

#include <algorithm>  
#include <iostream>    
#include <string>
#include <stack>
#include <vector>
#include <queue> 
#include <list> 

using namespace std;

string remove_k_digits(string num, int k) 
{
    string ans="";
    for(char &c:num)
    {
        while(ans.size() && ans.back()>c &&k)
        {
            ans.pop_back();
            k--;
        }
        if(ans.size()||c!='0')ans.push_back(c);
    }
    while(ans.size()&&k--) 
    {
        ans.pop_back();
    }
    return (ans=="")?"0":ans;
}

int main()
{ 
    string s = "1432219";
    int k = 3;

    string result = remove_k_digits(s, k);


    cout<<"Result is "<<result<<endl;

    return 0;

}

Output:

Result is 1219

 

 

Write a Comment

Leave a Comment

Your email address will not be published. Required fields are marked *