Minimum Adjacent Swaps to Reach the Kth Smallest Number LeetCode solution in Python

1
# Runtime: 1243 ms (Top 52.9%) | Memory: 16.52 MB (Top 32.4%)
2

3

4
class Solution:
5
    def getMinSwaps(self, num: str, k: int) -> int:
6
        num = list(num)
7
        orig = num.copy()
8

9
        for _ in range(k):
10
            for i in reversed(range(len(num) - 1)):
11
                if num[i] < num[i + 1]:
12
                    ii = i + 1
13
                    while ii < len(num) and num[i] < num[ii]:
14
                        ii += 1
15
                    num[i], num[ii - 1] = num[ii - 1], num[i]
16
                    lo, hi = i + 1, len(num) - 1
17
                    while lo < hi:
18
                        num[lo], num[hi] = num[hi], num[lo]
19
                        lo += 1
20
                        hi -= 1
21
                    break
22

23
        ans = 0
24
        for i in range(len(num)):
25
            ii = i
26
            while orig[i] != num[i]:
27
                ans += 1
28
                ii += 1
29
                num[i], num[ii] = num[ii], num[i]
30
        return ans