Solution Explanation: Minimum Adjacent Swaps to Reach the Kth Smallest Number

This problem asks for the minimum number of adjacent swaps required to transform a given number string num into the k-th smallest lexicographically larger permutation of its digits. The solution involves two main steps:

1. Finding the k-th smallest permutation:

We iteratively find the next lexicographically larger permutation of the digits in num using the next_permutation function (implementation varies slightly across languages). This function is applied k times to obtain the target permutation (s). The standard next_permutation algorithm works by:

• Finding the largest index i such that num[i] < num[i+1]. If no such index exists, the permutation is the last one, and we've reached the end of the possible permutations.
• Finding the largest index j such that num[j] > num[i].
• Swapping num[i] and num[j].
• Reversing the subarray num[i+1:].

2. Calculating the minimum swaps:

Once the k-th smallest permutation (s) is found, we need to determine the minimum number of adjacent swaps to transform num into s. This is achieved using a clever mapping and inversion counting technique.

• Index Mapping: We create a mapping d that stores the indices of each digit in the original num. d[i] is a list of indices where digit i appears in num.
• Greedy Index Selection: We iterate through the target permutation s. For each digit in s, we greedily select the smallest available index from its corresponding list in d. This ensures we use indices as close to their original positions as possible, minimizing swaps. The selected indices are stored in the arr array.
• Inversion Count: Finally, we count the number of inversions in arr. An inversion is a pair of indices (i, j) such that i < j but arr[i] > arr[j]. Each inversion represents at least one adjacent swap required. The total number of inversions equals the minimum number of adjacent swaps.

Time Complexity:

• Finding the k-th permutation takes O(k * n), where n is the length of num. Each next_permutation call takes O(n) in the worst case.
• Creating the index mapping d takes O(n).
• Greedy index selection takes O(n).
• Counting inversions using nested loops takes O(n²).

Therefore, the overall time complexity is dominated by the inversion counting, resulting in O(k * n + n²).

Space Complexity:

The space complexity is O(n) due to the storage of num, s, d, idx, and arr.

Code Examples (Python):

from itertools import permutations
 
def getMinSwaps(num: str, k: int) -> int:
    nums = sorted(list(num))
    perms = list(permutations(nums))
    target_perm = list(perms[k-1])
    
    #Function to calculate minimum swaps
    def calculate_min_swaps(original,target):
        swaps = 0
        n = len(original)
        index_map = {}
        for i,digit in enumerate(original):
            index_map[digit] = index_map.get(digit,[])+[i]
        
        assigned_indices = {}
        for digit in target:
            idx = index_map[digit].pop(0)
            assigned_indices[digit]=idx
 
        current_permutation = list(original)
        for i in range(len(target)):
            if current_permutation[i]!=target[i]:
                target_idx = assigned_indices[target[i]]
                
                for j in range(i,target_idx):
                    current_permutation[j], current_permutation[j+1] = current_permutation[j+1], current_permutation[j]
                    swaps +=1
 
        return swaps
    
    return calculate_min_swaps(list(num),target_perm)
 
 

This solution directly finds the Kth permutation using itertools.permutations and then calculates swaps based on individual digit moves. The previous provided solutions use a more efficient next_permutation and inversion counting, but this example might be easier to understand for some. Note that for very large inputs, this approach will be slower than the next_permutation based approach due to the generation of all permutations.