402. Remove K Digits

Problem Statement

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

Example 1:

Input: num = "1432219", k = 3
Output: "1219"
Explanation: Remove the three digits 4, 3, and 2 to form the new number 1219 which is the smallest.

Example 2:

Input: num = "10200", k = 1
Output: "200"
Explanation: Remove the leading 1 and the number is 200. Note that the output must not contain leading zeroes.

Example 3:

Input: num = "10", k = 2
Output: "0"
Explanation: Remove all the digits from the number and it is left with nothing which is 0.

Constraints:

• 1 <= k <= num.length <= 105

• num consists of only digits.

• num does not have any leading zeros except for the zero itself.

Intuition

Approach:
Use the concept of Monoton stack,
Remove the elements that does not follow increasing property

If still elements are not removed then remove from last
edge case
112
Follows monoton property throughout
Now remove k from last, as they are large

Links

https://leetcode.com/problems/remove-k-digits/description/

Video Links

https://www.youtube.com/watch?v=cFabMOnJaq0&ab_channel=NeetCode

Approach 1:

C++

class Solution {
public:
    string removeKdigits(string num, int k) {
        if(num.size() ==k)
            return "0";
        stack<char> st;
        for(int i=0; i<num.size(); i++){
            while(!st.empty() and st.top() > num[i] and k>0){
                st.pop();
                k--;
            }

            st.push(num[i]);
        }
        if(k) while(k--){st.pop();}
        stack<char> s2;
        while(!st.empty()){
            s2.push(st.top());
            st.pop();
        }
        while(s2.size()>1 and s2.top() == '0')
            s2.pop();

        string ans="";
        while(!s2.empty()){
            ans += s2.top();
            s2.pop();
        }

        return ans;
    }
};

Approach 2:

C++

Approach 3:

C++

Approach 4:

C++

Similar Problems