Learning-competitive-coding/Remove_K_Digits.py at master · raniyer/Learning-competitive-coding · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
"""
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:
    def removeKdigits(self, num: str, k: int) -> str:
        n = len(num)
        if n == k: return "0"
        res = []
        for i in range(n):
            while k and res and res[-1] > num[i]:
                res.pop()
                k -= 1
            res.append(num[i])


        while k:
            res.pop()
            k -= 1

        return "".join(res).lstrip('0') or "0"