# Short Python, one O(n) and one RegEx

• ## O(n) Solution

Go through the digits from left to right, remove previous digits if that makes the number smaller (and if we still have to remove digits). Almost the same as the `prep` function from my solution to an earlier problem, which did basically the same except it maximized the number.

``````def removeKdigits(self, num, k):
out = []
for d in num:
while k and out and out[-1] > d:
out.pop()
k -= 1
out.append(d)
return ''.join(out[:-k or None]).lstrip('0') or '0'
``````

## Regex Solution

k times remove the leftmost digit followed by a smaller digit (or remove the last digit). Didn't think this would be fast enough, but it is :-)

``````def removeKdigits(self, num, k):
sub = re.compile('1[0]|2[01]|3[0-2]|4[0-3]|5[0-4]|6[0-5]|7[0-6]|8[0-7]|9[0-8]|.\$').sub
for _ in range(k):
num = sub(lambda m: m.group()[1:], num, 1)
return num.lstrip('0') or '0'``````

• Great solution! Thanks for sharing, I got stuck at the while loop at first. I was using "if" statement and couldn't get some of the test cases passed.
My accepted C++ version, the idea is the same as your Python code:

``````string removeKdigits(string num, int k) {
string sol;
if (k >= num.length()) return "0";

// while the last number is larger than the new one,
// keep poping out the last number until a smaller one appears
// e.g. 1234567890 k=3
for (int i = 0; i < num.length(); i++){
while (sol.length() != 0 && k > 0 && sol.back() > num[i]){
sol.pop_back();
k--;
}
sol.push_back(num[i]);
}

// for monotonically increasing string
// discard the last k digits
// e.g. 123456 k=3
while (k != 0){
k--;
sol.pop_back();
}

// for sol with leading zeros
// e.g. 10200 k=1
while(sol[0] == '0') sol.erase(0,1);

return sol.length() == 0 ? "0" : sol;

}
``````

• How about the test case, num = "100" k =1 , the expected result should be "10" rather than "0".

• @larrywang2014 No, "0" is correct. Check out the problem's Example 2 again.

• May I ask why it works? I cannot find any intuitive explanation for such algorithm...

• Nice solution. Here's my C++ implementation.

``````class Solution {
public:
string removeKdigits(string num, int k) {
vector<char> stk;

for (char c : num) {
while (k && !stk.empty() && stk.back() > c) {
stk.pop_back();
k--;
}
stk.push_back(c);
}
while (k > 0) {
k--;
stk.pop_back();
}

auto p = stk.begin();
while (p != stk.end() && *p == '0') p++;

return p == stk.end() ? string("0") : string(p, stk.end());
}
};
``````

• C++ version

``````class Solution {
public:
string removeKdigits(string num, int k) {
if(k>=num.size()) return "0";
string res="";
for(char c:num)
{
while(res.size()&&k&&res.back()>c)
{
res.pop_back();
k--;
}
if(c!='0'||(res.size()&&res[0]!='0'))
res.push_back(c);
}
while(k-->0) res.pop_back();
return res.size()?res:"0";
}
};``````

• This post is deleted!

• Hello, very nice solution.
I don't understand the `or None` in `''.join(out[:-k or None])`, what's the meaning?

• I don't understand the `or None` in `''.join(out[:-k or None])`, what's the meaning?

I join @Vinceeent in asking this question!

• This post is deleted!

In the frequent case when k = 0, `out[:-0]` returns no elements, but `-0 or None` evaluates to `None`, and `out[:None]` returns the entire list!