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
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.