# Python O(k^2) solution

• The observation is that the smallest number among the first `k + 1` characters has to be included in the solution. You can basically leverage this idea repeatedly. Every time when you find a smallest number among the next `k+1` characters, you can discard all the numbers on the left of that character.

``````    def removeKdigits(self, num, k):
def helper(index, k, prefix):
#print index, k, prefix
if k is 0:
return prefix + num[index:]
if len(num) - index == k:
return prefix
mini = index
for i in xrange(index, index+k+1):
if num[i] < num[mini]:
mini = i
return helper(mini+1, k - (mini - index), prefix + num[mini])

result = helper(0, k, "").lstrip("0")
return result if result else "0"
``````

• @newman2 It's not O(k^2). It's O(kn).

• @cslns I think it's not even O(kn). Consider inputs like `num = 'a' * n` with fixed `k = 1`. With O(kn), this would be O(n). But it goes through the whole string and at every single character the `prefix + num[mini]` takes Θ(`len(prefix)`) time and space. And the space adds up as well, because each recursion level holds on to its `prefix`.

I think it's only something like O(n ⋅ max(n, k)) time and O(n2) space.

• @StefanPochmann recursion is a bad idea as I mentioned in my post: https://discuss.leetcode.com/topic/59985/python-recursive-and-iterative-solutions

Yes, recursion takes a lot of space for a long string and a large k value.

The worst case is to scan the whole string for each step. So should it be O(kn)? k is a variable not a constant here. It can be as large as n. Of course, if k = n we just return '0'. But for @newman2 's solution, we need to scan n times if all the characters in num is same like: num='1111111111', k = 10.

So I say it is O(kn) not O(n), or more precisely should be O(min(k,n) * n) not max(k,n).

• @cslns No, as explained it isn't O(kn). And it isn't O(min(k,n) * n), either, for the same reason.

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