# Nhut Nguyen # 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 <= 10^5`.

• `num` consists of only digits.

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

# Solution 1: Removing big digits of `num`

The problem can be performed in `k` steps. For each step you remove just one digit. In order to get the smallest integer, you have to remove the first digit that is bigger its next one.

## Example 1

• For `num = "1432219"`, you remove `4` (`> 3`) in the first step and get `num = "132219"`.

• Next, you remove `3` (`> 2`) to get `num = "12219"`.

• Finally, you remove `2` (`> 1`) to get `num = "1219"`.

## Code

``````#include <iostream>
using namespace std;
string removeKdigits(string num, int k) {
if (k == num.length()) {
return "0";
}
int i = 0;
while (k > 0) {
// find the digit to remove
while (i < num.length() - 1 && num[i] <= num[i+1]) {
i++;
}
// remove the digit and update where to find next
i = num.erase(num.begin() + i) - num.begin() - 1;
if (i < 0) {
i = 0;
}
k--;
}
i = 0;
while (i < num.length() && num[i]=='0') {
i++;
}
num.erase(num.begin(), num.begin() + i);
return num.empty() ? "0" : num;
}
int main() {
cout << removeKdigits("1432219", 3) << endl;
cout << removeKdigits("10200", 1) << endl;
cout << removeKdigits("10", 2) << endl;
}
``````
``````Output:
1219
200
0
``````

## Complexity

• Runtime: `O(kN)`, where `N = num.length`.

• Extra space: `O(1)`.

# Solution 2: Using `std::list` for faster erasure

The complexity of the `string::erase` in the loop of Solution 1 is not constant (`O(1)`). You can use `list::erase` for that performance.

## Code

``````#include <iostream>
#include <list>
using namespace std;
string removeKdigits(string num, int k) {
if (k == num.length()) {
return "0";
}
list<char> lnum(num.begin(), num.end());
auto it = lnum.begin();
while (k > 0) {
// find the digit to remove
while (it != prev(lnum.end()) && *it <= *(next(it))) {
it++;
}
// remove the digit and update where to find next
it = prev(lnum.erase(it));
k--;
}
it = lnum.begin();
while (it != lnum.end() && *it == '0') {
it = lnum.erase(it);
}
return lnum.empty() ? "0" : string(lnum.begin(), lnum.end());
}

int main() {
cout << removeKdigits("1432219", 3) << endl; // 1219
cout << removeKdigits("10200", 1) << endl; // 200
cout << removeKdigits("10", 2) << endl; // 0
}
``````
``````Output:
1219
200
0
``````

## Complexity

• Runtime: `O(N)`, where `N = num.length`.

• Extra space: `O(N)`.

# Some other ways to improve the performance

1. You can use `std::forward_list` instead of `std::list` to reduce the space complexity.

2. You can also construct the result from scratch by adding digits, not by removing them. This wil give the best performance but might not be easy to read code.