Remove K Digits

Question

Given a non-negative integer num represented as a string, remove k digits from the number so that the new number is the smallest possible.

Note:

• The length of num is less than 10002 and will be ≥ k.
• The given num does not contain any leading zero.

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.

Tags

• Stack
• Greedy

Thought

reference: https://discuss.leetcode.com/topic/59380/short-python-one-o-n-and-one-regex

Use the stack to store the result and check the top of the stack with every element in the string. If the element in the string is smaller than the top of the stack, pop the stack and minus k with 1. After that, push the element into stack as the new top element.

Code

class Solution(object):
    def removeKdigits(self, num, k):
        """
        :type num: str
        :type k: int
        :rtype: str
        """
        stack = []
        for ch in num:
            while k > 0 and stack and stack[-1] > ch:
                stack.pop()
                k -= 1
            stack.append(ch)

        index = 0
        while index < len(stack) and stack[index] == '0':
            index += 1
        if k > 0:
            result = stack[index:-k]  
        else:
            result = stack[index:]
        if len(result) == 0:
            return '0'
        else:
            return ''.join(result)