# Python recursive and iterative solutions

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

• The middle one doesn't work. (now does)

• thanks. It should be

`````` while i < k and num:
``````

updated

• Two possible improvements for it:

• count down `k` instead of using `i`
• `return num or '0'`

• @StefanPochmann thank you for the tips. updated

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.