## Saturday, July 22, 2017

### [Leetcode] Remove K Digits, Solution

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.```

[Thoughts]

[Code]
``````1:    string removeKdigits(string num, int k) {
2:      string res = "";
3:
4:      for(int i =0; i<num.size(); i++) {
5:        while(res.size()>0 && res.back() > num[i]&& k>0) {
6:          res.pop_back();
7:          k--;
8:        }
9:        res.push_back(num[i]);
10:      }
11:
12:      // if k != 0, remove the digit from right
13:      res.erase(res.size() - k, k);
14:
15:      // trim the zero
16:      int i =0;
17:      while(res[i] == '0' && i<res.size()-1) i++;
18:
19:      res.erase(0, i);
20:
21:      return res.size() == 0? "0": res;
22:    }
``````