"""

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.

2019/02/14: 1st Attempt after reading answer

"""


class Solution:
    def removeKdigits(self, num: 'str', k: 'int') -> 'str':
        """

        :param num:
        :param k:
        :return:

        Time complexity: O(n)
        Space complexity: O(n)

        """

        if len(num) <= k:
            return '0'

        stack = []
        for n in num:
            while stack and stack[-1] > n and k > 0:
                stack.pop()
                k -= 1
            stack.append(n)

        # Not enough digits removed
        while stack and k > 0:
            stack.pop()
            k -= 1

        while stack and stack[0] == '0':
            stack.pop(0)
        if stack:
            return ''.join(stack)
        else:
            return '0'


if __name__=='__main__':

    sol = Solution()

    cases = [

        (sol.removeKdigits, ("1432219",3), "1219"),
        (sol.removeKdigits, ("10200",1), "200"),
        (sol.removeKdigits, ("10",2), "0"),
        (sol.removeKdigits, ("10",1), "0"),
        (sol.removeKdigits, ("100",1), "0"),
        (sol.removeKdigits, ("112",1), "11"),


             ]

    for i, (func, case, expected) in enumerate(cases):
        ans = func(*case)
        if ans == expected:
            print("Case {:d} Passed".format(i + 1))
        else:
            print("Case {:d} Failed; Expected {:s} != Output {:s}".format(i+1, str(expected), str(ans)))
