1
# Lets make monotonically growing stack and save the indexes of popped elements into deletes dict.
2
# as soon as len(delete) == k delete those indexes from the initial string and thats the answer.
3
# if len(delete) < k remove k-len(delete) chars from right and thats the answer
4
class Solution:
5
    def removeKdigits(self, s: str, k: int) -> str:
6
        if len(s) == k:
7
            return "0"
8
        stack = []
9
        delete = {}
10
        for i in range(len(s)):
11

12
            while stack and s[i] < stack[-1][0]:
13
                delete[stack.pop()[1]] = 1
14
                if len(delete) == k:
15
                    break
16
            if len(delete) == k:
17
                return self.deleteindexes(s, delete, k)
18
            stack.append([s[i], i])
19
        s1 = self.deleteindexes(s, delete, k)
20

21
        return str(int(s1[: len(s1) - k + len(delete)]))
22

23
    def deleteindexes(self, s, delete, k):
24
        if not delete:
25
            return s
26
        if len(delete) == k:
27
            return str(
28
                int("".join([c for ind, c in enumerate(s) if ind not in delete]))
29
            )
30
        else:
31
            return "".join([c for ind, c in enumerate(s) if ind not in delete])