## Challenge#

Given a non-negative number represented as a string, return the smaller possible integer after removing K digits.
E.g

``````"1041"
1
``````

Will output `41`

## Solution 1#

I really liked my first solution, however performances can’t be worst.
It’s a brute force approach doing backtracking, basically I tried to remove 3 digits in every possible position.

``````from copy import deepcopy
class Solution:
def helper(self, num, k, arr, start):
if len(arr) == k:
self.res.append(deepcopy(arr))
return
for i in range(start, len(num)):
arr.append(i)
self.helper(num, k, arr, i+1)
arr.remove(i)
return

def remove_from_list(self, num, to_remove):
num = list(num)
r = []
for i, e in enumerate(num):
if i not in to_remove:
r.append(e)
return r

def removeKdigits(self, num: str, k: int) -> str:
if k == len(num):
return  "0"
self.res = []
self.helper(tuple(num), k, [], 0)
r = int(num)
for i in self.res:
ret = self.remove_from_list(num, i)
ret =  int("".join(ret))
r  = min(r, ret)
return str(r)

``````

## Solution 2#

After failing on a lot of different test cases it looks like this greedy implementation below works.

I still had to handle some edge cases e.g `1112`, 2 must be remove but in `1041` first 1 needs to be removed.

``````class Solution:

def remove_zero_in_front(self, string):
i = 0
while i < len(string) and string[i] == "0":
i += 1
return string[i:]

def find_biggest_and_remove(self, num):
m = 0
for i in (num):
m = max(m, int(i))
num = list(num)
snum = "".join(num)
pos = snum.find(str(m))
newstr = num[:pos] + num[pos+1:]
return "".join(newstr)

def removeKdigits(self, num: str, k: int) -> str:
if k >= len(num):
return "0"
i = 1
num = list(num)
while i < len(num) and k > 0:
if num[i-1] > num[i]:
num.pop(i-1)
i = 0
k -= 1
i += 1
res = "".join(num)
while k > 0:
res = self.find_biggest_and_remove(res)
k-=1
res = self.remove_zero_in_front(res)
if res == "":
return "0"
return res
``````

Time complexity: n*n
Space complexity: n