Verbose but intuitive python solution which passes


  • 0

    Since the smallest number is the one with sorted digits (1234 < 4321), we need to find digits which break sort order and fix them.

    Instead of in-place modification of num, I use sets to remember which digits' indices are removed

    class Solution(object):
        def go_back(self, r):
            l = r-1
            while l >= 0 and self.k > 0:
                if l not in self.removed:
                    if self.num[l] > self.num[r]:
                        self.removed.add(l)
                        self.k -= 1
                    else:
                        break
                l -= 1
    
        def follow_sort_order(self):
            prev = self.num[0]
            for i in xrange(1, len(self.num)):
                if self.k <= 0:
                    break
    
                if self.num[i] < prev:
                    self.go_back(i)
    
                prev = self.num[i]
    
        def remove_tail(self):
            for i in xrange(len(self.num)-1, -1, -1):
                if self.k <= 0:
                    break
                if i in self.removed:
                    continue
                self.removed.add(i)
                self.k -= 1
    
        def remove_zeros(self):
            done = False
            str = ""
            i = -1
            for c in self.num:
                i += 1
                if c == '0' and not done or i in self.removed:
                    continue
                else:
                    str += c
                    done = True
            if str == "":
                return "0"
            return str
    
        def removeKdigits(self, num_init, k_init):
            self.k = k_init
            self.removed = set()
            self.num = num_init
    
            self.follow_sort_order()
            self.remove_tail()
            str = self.remove_zeros()
            return str
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.