Leetcode 1505. Minimum Possible Integer After at Most K Adjacent Swaps On Digits

Problem statement

https://leetcode.com/problems/???/

Solution

The idea is to try to put the smallest digit to the first place: we need to know where the closest 0 is, closest 1 and so on. For each digit we keep deque of places where this digit is. Also we keep sorted list of visited indexes. On each step we try 0, 1, 2, .., 9 and evaluate step: how many swaps we need to do to get this digits on its place. Actually it equal to index - seen.bisect(index), see cases 9999901 and 9999910 to get more details.

Complexity

Time complexity is O(n * log n).

Code

from sortedcontainers import SortedList

class Solution:
    def minInteger(self, num, k):
        places, n = defaultdict(deque), len(num)
        for i, d in enumerate(num):
            places[d].append(i)
        ans, seen = "", SortedList()

        while k > 0 and len(seen) != n:
            for d in digits:
                if places[d]:
                    index = places[d][0]
                    steps = index - seen.bisect(index)
                    if steps <= k:
                        k, ans = k - steps, ans + d
                        places[d].popleft()
                        seen.add(index)
                        break
        
        return ans + "".join(s for i,s in enumerate(num) if i not in seen)