## 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'
```