Given string num representing a non-negative integer num, and an integer k, return the smallest possible integer after removing k digits from num.
Example 1: Input: num = “1432219”, k = 3 Output: “1219” Explanation: Remove the three digits 4, 3, and 2 to form the new number 1219 which is the smallest. Example 2: Input: num = “10200”, k = 1 Output: “200” Explanation: Remove the leading 1 and the number is 200. Note that the output must not contain leading zeroes. Example 3: Input: num = “10”, k = 2 Output: “0” Explanation: Remove all the digits from the number and it is left with nothing which is 0.
Constraints:
1 <= k <= num.length <= 105
num consists of only digits.
num does not have any leading zeros except for the zero itself.
- code
class Solution:
def removeKdigits(self, num: str, k: int) -> str:
# while num and num[0] == "0":
# num = num[1:]
num = num.lstrip("0")
if k == 0: return num or "0"
i = 1
while i < len(num):
if num[i-1] > num[i]:
return self.removeKdigits(num[:i-1] + num[i:], k - 1)
if i == len(num) - 1:
return self.removeKdigits(num[:i], k - 1)
i += 1
return "0" # "9", k = 1
- code
class Solution:
def removeKdigits(self, num: str, k: int) -> str:
stack = []
for v in num:
while stack and k and v < stack[-1]:
stack.pop()
k -= 1
stack.append(v)
if k: stack = stack[:-k]
return "".join(stack).lstrip("0") or "0"