402. Remove K Digits

402. Remove K Digits (Medium)

Given a non-negative integer num represented as a string, remove k digits from the number so that the new number is the smallest possible.

Note:

• The length of num is less than 10002 and will be ≥ k.
• The given num does not contain any leading zero.

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.

Related Topics:
Stack, Greedy

Similar Questions:

• Create Maximum Number (Hard)
• Monotone Increasing Digits (Medium)
• Find the Most Competitive Subsequence (Medium)

Solution 1. Mono Stack

Intuition

We want the answer as lexigraphically smaller as possible, so we should use a mono-increasing stack which will keep tightening towards lexigraphically smaller result.

Algorithm

Use a string ans as a mono-increasing stack.

For each character in s, we push it into ans. And before pushing, we need to pop greater characters in ans first.

For each character we popped, we need to decrement k. And we only keep popping of k > 0.

If after traversing all characters in s, k is still not exhausted, we pop back from s until k == 0.

Lastly, removing leading zeros.

// OJ: https://leetcode.com/problems/remove-k-digits/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(N)
class Solution {
public:
    string removeKdigits(string s, int k) {
        if (k == s.size()) return "0";
        string ans;
        for (int i = 0, N = s.size(); i < N; ++i) {
            while (k > 0 && ans.size() && s[i] < ans.back()) {
                ans.pop_back();
                --k;
            }
            ans.push_back(s[i]);
        }
        while (k > 0) {
            ans.pop_back();
            --k;
        }
        int i = 0;
        while (i < ans.size() && ans[i] == '0') ++i;
        return i == ans.size() ? "0" : ans.substr(i);
    }
};

Or

// OJ: https://leetcode.com/problems/remove-k-digits/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(N)
class Solution {
public:
    string removeKdigits(string s, int k) {
        string ans;
        for (int i = 0, N = s.size(); i < N; ++i) {
            while (ans.size() && i - ans.size() < k && s[i] < ans.back()) ans.pop_back(); // We've visited `i` elements and kept `ans.size()` elements, so we've removed `i - ans.size()` elements. If `i - ans.size() < k`, we can continue popping; otherwise, we should stop popping because that will result in excessive popping.
            if (ans.size() < N - k) ans.push_back(s[i]); // We can only keep exactly `N - k` elements in `ans`, so we only push if `ans.size < N - k`.
        }
        auto begin = ans.find_first_not_of('0');
        return begin == string::npos ? "0" : ans.substr(begin);
    }
};