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