First, I tried recursive solution, but I got memory limited exceeded for long string and large k value

```
def removeKdigits(self, num, k):
# memory limite exceed for recursive
if k == 0 or num == '': return num if num else '0'
i = 0
while i+1 < len(num) and int(num[i+1]) >= int(num[i]):
i += 1
return self.removeKdigits(num.replace(num[i],'', 1).lstrip('0'), k-1)
```

Then, I tried iterative solution, with the complexity of O(kn)

```
def removeKdigits(self, num, k):
while k > 0 and num:
j = 0
while j+1<len(num) and num[j+1] >= num[j]:
j += 1
num = num.replace(num[j],'',1).lstrip('0')
k -= 1
return num or '0'
```

Then I realized that I can do it with O(n) complexity but requiring O(n) space

```
def removeKdigits(self, num, k):
ret = []
for i in num:
while k > 0 and ret and ret[-1] > i:
ret.pop()
k -= 1
ret.append(i)
if k != 0: ret = ret[:len(ret)-k]
ret = ''.join(ret).lstrip('0')
return ret if ret else '0'
```