Skip to content

Latest commit

 

History

History
86 lines (63 loc) · 3.72 KB

README.md

File metadata and controls

86 lines (63 loc) · 3.72 KB

402. Remove K Digits (Medium)

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.

Companies:
Amazon, Microsoft, Adobe, MakeMyTrip

Related Topics:
String, Stack, Greedy, Monotonic Stack

Similar Questions:

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 s[i], we push it into ans. And before pushing, we need to pop ans.back() if

  1. we have delete allowance -- i - ans.size() < k where i - ans.size() is the number of deleted characters.
  2. ans.back() > s[i]

Only pop strictly greater characters. Consider example s = "112", k = 1 and s = "110", k = 1. We need to keep both 1s, and determine whether we want to pop the 1s when we look at the character(s) after them.

Don't put characters beyond N - k window: Any characters that lands beyond window N - k should be deleted right away because they are no better than those within the window.

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 (s.size() == k) return "0";
        string ans;
        for (int i = 0, N = s.size(); i < N; ++i) {
            while (i - ans.size() < k && ans.size() && ans.back() > s[i]) ans.pop_back(); // if we have delete allowance and `ans.back()` is greater than `s[i]`, we pop `ans.back()`
            if (ans.size() < N - k) ans.push_back(s[i]); // any character that was ever left beyond the valid window should be deleted.
        }
        auto i = ans.find_first_not_of('0'); // remove leading `0`s
        return i == string::npos ? "0" : ans.substr(i);
    }
};