402.Remove K Digits

Tags: [greedy], [stack]

Link: https://leetcode.com/problems/remove-k-digits/?tab=Description

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.

class Solution(object):
    def removeKdigits(self, num, k):
        """
        :type num: str
        :type k: int
        :rtype: str
        """
        if not num:
            return '0'

        stack = []
        index = 0
        while index < len(num):
            curr = int(num[index])
            while k > 0 and stack and stack[-1] > curr:
                stack.pop()
                k -= 1

            stack.append(curr)
            index += 1

        # corner case: k is still not used out. i.e. num = '111111', k = 3.
        # Because len(num) >= k, 
        # so here we don't need to check whether the stack is empty or not.
        while k > 0:
            stack.pop()
            k -= 1

        # build the result
        result = []
        while stack:
            result.append(stack.pop())

        result.reverse()

        # remove the leading zeros.
        start = 0
        while start < len(result):
            if result[start] != 0:
                break
            start += 1

        if not result[start:]:
            return '0'
        else:
            return ''.join([str(x) for x in result[start:]])

Revelation:

• Sometime, we should first think whether we can use greedy approach to solve the problem. For this question, the reason why we can apply greedy approach is that to achieve our goal, we should try to remove the left most, and bigger digit from left to right, until we use out of the k.

Note:

• Time complexity = O(n), n is the length of the given num.

Time Limited Exceeded

import sys

class Solution(object):
    def __init__(self):
        self.min_num = sys.maxint

    def removeKdigits(self, num, k):
        """
        :type num: str
        :type k: int
        :rtype: str
        """
        buff = []
        self.remove_k_digits_helper(num, k, 0, buff)
        return self.min_num

    def remove_k_digits_helper(self, num, k, index, buff):
        # base case
        if index >= len(num):
            if k == 0:
                new_num = 0
                if buff:
                    new_num = int(''.join(buff))
                self.min_num = min(self.min_num, new_num)
            return

        # remove the current digit
        self.remove_k_digits_helper(num, k - 1, index + 1, buff)

        # not remove the current digit
        buff.append(num[index])
        self.remove_k_digits_helper(num, k, index + 1, buff)
        buff.pop()

Revelation:

• Brute force, try all possible ways to remove the k digits.
• For each digit, we have two choices, one is keeping it, and the other is removing it.

Note:

• Time complexity = O(2^n), n is the length of the given num. For each digit we can either choose keep it or remove it.