LeetCode-in-Java

1850. Minimum Adjacent Swaps to Reach the Kth Smallest Number

Medium

You are given a string num, representing a large integer, and an integer k.

We call some integer wonderful if it is a permutation of the digits in num and is greater in value than num. There can be many wonderful integers. However, we only care about the smallest-valued ones.

For example, when num = "5489355142":
- The 1^st smallest wonderful integer is "5489355214".
- The 2^nd smallest wonderful integer is "5489355241".
- The 3^rd smallest wonderful integer is "5489355412".
- The 4^th smallest wonderful integer is "5489355421".

Return the minimum number of adjacent digit swaps that needs to be applied to num to reach the k^th smallest wonderful integer.

The tests are generated in such a way that k^th smallest wonderful integer exists.

Example 1:

Input: num = “5489355142”, k = 4

Output: 2

Explanation: The 4^th smallest wonderful number is “5489355421”. To get this number:

Swap index 7 with index 8: “5489355142” -> “5489355412”
Swap index 8 with index 9: “5489355412” -> “5489355421”

Example 2:

Input: num = “11112”, k = 4

Output: 4

Explanation: The 4^th smallest wonderful number is “21111”. To get this number:

Swap index 3 with index 4: “11112” -> “11121”
Swap index 2 with index 3: “11121” -> “11211”
Swap index 1 with index 2: “11211” -> “12111”
Swap index 0 with index 1: “12111” -> “21111”

Example 3:

Input: num = “00123”, k = 1

Output: 1

Explanation: The 1^st smallest wonderful number is “00132”. To get this number:

Swap index 3 with index 4: “00123” -> “00132”

Constraints:

2 <= num.length <= 1000
1 <= k <= 1000
num only consists of digits.

Solution

public class Solution {
    public int getMinSwaps(String num, int k) {
        char[] result = num.toCharArray();
        while (--k >= 0) {
            int swap = result.length - 2;
            while (swap >= 0 && result[swap] >= result[swap + 1]) {
                --swap;
            }
            int pair = result.length - 1;
            while (pair > swap && result[swap] >= result[pair]) {
                --pair;
            }
            swap(result, swap, pair);
            int lo = swap + 1;
            int hi = result.length - 1;
            while (lo < hi) {
                swap(result, lo++, hi--);
            }
        }
        int ans = 0;
        char[] arr = num.toCharArray();
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == result[i]) {
                continue;
            }
            int j = i;
            while (arr[i] != result[j]) {
                ++j;
            }
            ans += j - i;
            while (--j >= i) {
                swap(result, j, j + 1);
            }
        }
        return ans;
    }

    private void swap(char[] arr, int a, int b) {
        char tmp = arr[a];
        arr[a] = arr[b];
        arr[b] = tmp;
    }
}

This site is open source. Improve this page.