Problem Description

Given a string num representing a positive integer and an integer k, you are asked to find the minimum number of adjacent swaps required to transform num into its k-th smallest permutation (in lexicographical order). Each swap can only exchange two adjacent digits.

• You must find the k-th smallest permutation that is strictly larger than the current num.
• Only adjacent swaps are allowed (e.g., swapping digits at indices i and i+1).
• Each digit can only be used once per swap, and you cannot reuse a digit in the same swap operation.
• There is always at least one valid answer.

Thought Process

At first glance, the problem seems to require generating all permutations of the string until reaching the k-th one, then counting swaps. However, generating all permutations is highly inefficient, especially for long numbers.

Instead, we can observe that:

• We only need to find the k-th next permutation (not all permutations).
• Once we have the target permutation, we can count how many adjacent swaps are needed to transform the original string into this target.

1. Efficiently find the k-th next lexicographical permutation of num.
2. Calculate the minimum number of adjacent swaps required to reach this permutation from the original number.

Solution Approach

Let's break down the solution into clear steps:

1. Find the k-th Next Permutation:
   • Use the standard next permutation algorithm to iteratively generate the next lexicographical permutation of the string k times.
   • This avoids generating all permutations and is efficient (O(n) per permutation, where n is the number of digits).
2. Count Minimum Adjacent Swaps:
   • Now, with the target permutation, we need to count the minimum number of adjacent swaps to transform the original string into the target.
   • Iterate through each digit of the original string. For each position, if the digit doesn't match the target, find the position of the correct digit (from the target) in the current string, and swap it leftwards (using adjacent swaps) until it reaches its correct position.
   • Each leftward move counts as one swap. We repeat this for every mismatch.

This approach works because moving a digit leftward to its correct position using adjacent swaps is always optimal and doesn't affect the order of earlier digits.

Example Walkthrough

Let's walk through an example to see how the process works:

Input: num = "5489355142", k = 4

1. Find the 4th next permutation:
   • Apply the next permutation algorithm 4 times to get the target permutation: ["5489355412", "5489355421", "5489359124", "5489359142"].
   • The 4th permutation is "5489359142".
2. Count swaps to reach the target:
   • Start comparing digits from left to right. Whenever a digit doesn't match, find the matching digit in the current string (to the right), and swap it leftwards until it matches the target position, counting each swap.
   • For this example, the process would involve moving the '9' digit to the correct place, then adjusting other digits as needed, summing up the total number of swaps.
3. Result:
   • The minimum number of adjacent swaps required is 3.

Time and Space Complexity

• Brute-force approach: Generating all permutations is O(n!), which is infeasible for even moderate values of n.
• Optimized approach:
  • Finding the next permutation k times is O(k * n), where n is the length of num.
  • Counting swaps is O(n^2) in the worst case, since for each digit, we may need to scan and swap through up to n positions.
  • Therefore, total time complexity is O(k * n + n^2).
  • Space complexity is O(n), mainly for storing the target permutation as a list and possibly a working copy of the string.

Summary

The problem is elegantly solved by decomposing it into two manageable subproblems: efficiently finding the k-th next permutation using the standard algorithm, and then counting the minimum adjacent swaps needed to reach this permutation from the original string. By focusing on adjacent swaps and leveraging the properties of permutations, we avoid brute-force methods and achieve an efficient, practical solution. This approach demonstrates the power of breaking complex problems into logical steps and applying well-known algorithms in creative ways.

Code Implementation

class Solution:
    def getMinSwaps(self, num: str, k: int) -> int:
        def next_permutation(arr):
            n = len(arr)
            i = n - 2
            while i >= 0 and arr[i] >= arr[i + 1]:
                i -= 1
            if i == -1:
                return False
            j = n - 1
            while arr[j] <= arr[i]:
                j -= 1
            arr[i], arr[j] = arr[j], arr[i]
            arr[i + 1:] = reversed(arr[i + 1:])
            return True

        original = list(num)
        target = list(num)
        for _ in range(k):
            next_permutation(target)

        swaps = 0
        temp = original[:]
        for i in range(len(temp)):
            if temp[i] != target[i]:
                j = i + 1
                while temp[j] != target[i]:
                    j += 1
                while j > i:
                    temp[j], temp[j - 1] = temp[j - 1], temp[j]
                    swaps += 1
                    j -= 1
        return swaps
      

class Solution {
public:
    int getMinSwaps(string num, int k) {
        string target = num;
        for (int i = 0; i < k; ++i) {
            next_permutation(target.begin(), target.end());
        }
        int swaps = 0;
        string temp = num;
        int n = temp.size();
        for (int i = 0; i < n; ++i) {
            if (temp[i] != target[i]) {
                int j = i + 1;
                while (temp[j] != target[i]) ++j;
                while (j > i) {
                    swap(temp[j], temp[j - 1]);
                    swaps++;
                    j--;
                }
            }
        }
        return swaps;
    }
};
      

class Solution {
    public int getMinSwaps(String num, int k) {
        char[] target = num.toCharArray();
        for (int i = 0; i < k; ++i) {
            nextPermutation(target);
        }
        char[] temp = num.toCharArray();
        int swaps = 0;
        int n = temp.length;
        for (int i = 0; i < n; ++i) {
            if (temp[i] != target[i]) {
                int j = i + 1;
                while (temp[j] != target[i]) j++;
                while (j > i) {
                    char t = temp[j];
                    temp[j] = temp[j - 1];
                    temp[j - 1] = t;
                    swaps++;
                    j--;
                }
            }
        }
        return swaps;
    }

    private void nextPermutation(char[] arr) {
        int n = arr.length, i = n - 2;
        while (i >= 0 && arr[i] >= arr[i + 1]) i--;
        if (i >= 0) {
            int j = n - 1;
            while (arr[j] <= arr[i]) j--;
            char t = arr[i];
            arr[i] = arr[j];
            arr[j] = t;
        }
        reverse(arr, i + 1, n - 1);
    }

    private void reverse(char[] arr, int l, int r) {
        while (l < r) {
            char t = arr[l];
            arr[l++] = arr[r];
            arr[r--] = t;
        }
    }
}
      

var getMinSwaps = function(num, k) {
    function nextPermutation(arr) {
        let n = arr.length, i = n - 2;
        while (i >= 0 && arr[i] >= arr[i + 1]) i--;
        if (i >= 0) {
            let j = n - 1;
            while (arr[j] <= arr[i]) j--;
            [arr[i], arr[j]] = [arr[j], arr[i]];
        }
        let l = i + 1, r = n - 1;
        while (l < r) {
            [arr[l], arr[r]] = [arr[r], arr[l]];
            l++; r--;
        }
    }

    let original = num.split('');
    let target = num.split('');
    for (let i = 0; i < k; ++i) {
        nextPermutation(target);
    }
    let swaps = 0;
    let temp = original.slice();
    for (let i = 0; i < temp.length; ++i) {
        if (temp[i] !== target[i]) {
            let j = i + 1;
            while (temp[j] !== target[i]) j++;
            while (j > i) {
                [temp[j], temp[j - 1]] = [temp[j - 1], temp[j]];
                swaps++;
                j--;
            }
        }
    }
    return swaps;
};