Minimum Adjacent Swaps to Reach the Kth Smallest Number

To solve this problem, we need to simulate the next permutation operation k times and then count the swaps needed to turn num into the kth wonderful integer.

 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
class Solution:
    def getMinSwaps(self, num: str, k: int) -> int:
        def next_permutation(arr):
            # Generate the next permutation in lexicographical order
            i = j = len(arr) - 1
            while i > 0 and arr[i-1] >= arr[i]:
                i -= 1
            if i == 0:   # arr is in descending order
                arr.reverse()
                return
            k = i - 1    # Find the last "ascending" position
            while arr[j] <= arr[k]:
                j -= 1
            arr[k], arr[j] = arr[j], arr[k]  
            l, r = k + 1, len(arr) - 1  # Reverse the second part
            while l < r:
                arr[l], arr[r] = arr[r], arr[l]
                l += 1
                r -= 1

        num_list = list(num)
        for _ in range(k):
            next_permutation(num_list)
        num_kth = ''.join(num_list)

        # Count the swaps required to turn `num` into `num_kth`
        num_list, num_kth_list = list(num), list(num_kth)
        swaps = 0
        for i in range(len(num_list)):
            j = i
            while num_list[i] != num_kth_list[j]:
                j += 1
            num_kth_list[i:j+1] = [num_kth_list[j]] + num_kth_list[i:j]
            swaps += j - i
        return swaps

In this code, next_permutation is a helper function that generates the next lexicographical permutation of arr. It works by identifying the last “ascending” position in arr, swapping this position with the smallest larger element in the rest of the array, and then reversing the tail of the array.

The main part of getMinSwaps transforms num into a list of characters, applies next_permutation k times, and then counts the number of adjacent swaps needed to turn num into the kth wonderful integer. This count is achieved by a linear scan and moving the j pointer until it finds the target element and then shifting the subarray one place to the right and moving the target element to the leftmost position. The distance that j has moved is the number of swaps made.