Problem

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 1st smallest wonderful integer is "5489355214".
    • The 2nd smallest wonderful integer is "5489355241".
    • The 3rd smallest wonderful integer is "5489355412".
    • The 4th smallest wonderful integer is "5489355421".

Return _theminimum number of adjacent digit swaps that needs to be applied to _num to reach thekth smallest wonderful integer.

The tests are generated in such a way that kth smallest wonderful integer exists.

Examples

Example 1

1
2
3
4
5

Input: num = "5489355142", k = 4
Output: 2
Explanation: The 4th smallest wonderful number is "5489355421". To get this number:
- Swap index 7 with index 8: "5489355 _14_ 2" -> "5489355 _41_ 2"
- Swap index 8 with index 9: "54893554 _12_ " -> "54893554 _21_ "

Example 2

1
2
3
4
5
6
7

Input: num = "11112", k = 4
Output: 4
Explanation: The 4th smallest wonderful number is "21111". To get this number:
- Swap index 3 with index 4: "111 _12_ " -> "111 _21_ "
- Swap index 2 with index 3: "11 _12_ 1" -> "11 _21_ 1"
- Swap index 1 with index 2: "1 _12_ 11" -> "1 _21_ 11"
- Swap index 0 with index 1: "_12_ 111" -> "_21_ 111"

Example 3

1
2
3
4

Input: num = "00123", k = 1
Output: 1
Explanation: The 1st smallest wonderful number is "00132". To get this number:
- Swap index 3 with index 4: "001 _23_ " -> "001 _32_ "

Constraints

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

Solution

Method 1 – Next Permutation + Greedy Swaps

Intuition

To reach the kth smallest wonderful integer, we generate the next permutation k times. To count the minimum adjacent swaps needed to transform the original string into the target permutation, we use a greedy two-pointer approach: for each position, move the required digit to its place using adjacent swaps.

Approach

  1. Convert the string to a list of digits.
  2. Generate the next permutation k times to get the target permutation.
  3. For each position, if the digit differs from the original, find the position of the required digit and swap it leftwards using adjacent swaps, counting each swap.
  4. Repeat for all positions.
  5. Return the total swap count.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

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 ans = 0;
        vector<char> arr(num.begin(), num.end());
        for (int i = 0; i < arr.size(); ++i) {
            if (arr[i] != target[i]) {
                int j = i;
                while (arr[j] != target[i]) ++j;
                while (j > i) {
                    swap(arr[j], arr[j-1]);
                    --j;
                    ++ans;
                }
            }
        }
        return ans;
    }
};
 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

func getMinSwaps(num string, k int) int {
    arr := []byte(num)
    target := make([]byte, len(arr))
    copy(target, arr)
    for i := 0; i < k; i++ {
        nextPermutation(target)
    }
    ans := 0
    for i := 0; i < len(arr); i++ {
        if arr[i] != target[i] {
            j := i
            for arr[j] != target[i] { j++ }
            for j > i {
                arr[j], arr[j-1] = arr[j-1], arr[j]
                j--
                ans++
            }
        }
    }
    return ans
}
func nextPermutation(arr []byte) {
    n := len(arr)
    i := n - 2
    for i >= 0 && arr[i] >= arr[i+1] { i-- }
    if i >= 0 {
        j := n - 1
        for arr[j] <= arr[i] { j-- }
        arr[i], arr[j] = arr[j], arr[i]
    }
    for l, r := i+1, n-1; l < r; l, r = l+1, r-1 {
        arr[l], arr[r] = arr[r], arr[l]
    }
}
 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

class Solution {
    public int getMinSwaps(String num, int k) {
        char[] arr = num.toCharArray();
        char[] target = arr.clone();
        for (int i = 0; i < k; ++i) nextPermutation(target);
        int ans = 0;
        for (int i = 0; i < arr.length; ++i) {
            if (arr[i] != target[i]) {
                int j = i;
                while (arr[j] != target[i]) ++j;
                while (j > i) {
                    char tmp = arr[j]; arr[j] = arr[j-1]; arr[j-1] = tmp;
                    --j;
                    ++ans;
                }
            }
        }
        return ans;
    }
    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 tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp;
        }
        for (int l = i+1, r = n-1; l < r; ++l, --r) {
            char tmp = arr[l]; arr[l] = arr[r]; arr[r] = tmp;
        }
    }
}
 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

class Solution {
    fun getMinSwaps(num: String, k: Int): Int {
        val arr = num.toCharArray()
        val target = arr.copyOf()
        repeat(k) { nextPermutation(target) }
        var ans = 0
        for (i in arr.indices) {
            if (arr[i] != target[i]) {
                var j = i
                while (arr[j] != target[i]) j++
                while (j > i) {
                    arr[j] = arr[j-1].also { arr[j-1] = arr[j] }
                    j--
                    ans++
                }
            }
        }
        return ans
    }
    private fun nextPermutation(arr: CharArray) {
        var i = arr.size - 2
        while (i >= 0 && arr[i] >= arr[i+1]) i--
        if (i >= 0) {
            var j = arr.size - 1
            while (arr[j] <= arr[i]) j--
            arr[i] = arr[j].also { arr[j] = arr[i] }
        }
        var l = i+1; var r = arr.size-1
        while (l < r) {
            arr[l] = arr[r].also { arr[r] = arr[l] }
            l++; r--
        }
    }
}
 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

def get_min_swaps(num: str, k: int) -> int:
    def next_perm(arr: list[str]) -> None:
        n = len(arr)
        i = n-2
        while i >= 0 and arr[i] >= arr[i+1]:
            i -= 1
        if i >= 0:
            j = n-1
            while arr[j] <= arr[i]:
                j -= 1
            arr[i], arr[j] = arr[j], arr[i]
        l, r = i+1, n-1
        while l < r:
            arr[l], arr[r] = arr[r], arr[l]
            l += 1
            r -= 1
    arr = list(num)
    target = arr[:]
    for _ in range(k):
        next_perm(target)
    ans = 0
    for i in range(len(arr)):
        if arr[i] != target[i]:
            j = i
            while arr[j] != target[i]:
                j += 1
            while j > i:
                arr[j], arr[j-1] = arr[j-1], arr[j]
                j -= 1
                ans += 1
    return ans
 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
36
37
38
39

impl Solution {
    pub fn get_min_swaps(num: String, k: i32) -> i32 {
        fn next_perm(arr: &mut Vec<char>) {
            let n = arr.len();
            let mut i = n-2;
            while i >= 0 && arr[i] >= arr[i+1] {
                if i == 0 { break; }
                i -= 1;
            }
            if i >= 0 {
                let mut j = n-1;
                while arr[j] <= arr[i] { j -= 1; }
                arr.swap(i, j);
            }
            let (mut l, mut r) = (i+1, n-1);
            while l < r {
                arr.swap(l, r);
                l += 1;
                r -= 1;
            }
        }
        let mut arr: Vec<char> = num.chars().collect();
        let mut target = arr.clone();
        for _ in 0..k { next_perm(&mut target); }
        let mut ans = 0;
        for i in 0..arr.len() {
            if arr[i] != target[i] {
                let mut j = i;
                while arr[j] != target[i] { j += 1; }
                while j > i {
                    arr.swap(j, j-1);
                    j -= 1;
                    ans += 1;
                }
            }
        }
        ans
    }
}
 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

class Solution {
    getMinSwaps(num: string, k: number): number {
        const arr = num.split('');
        const target = arr.slice();
        for (let i = 0; i < k; ++i) nextPerm(target);
        let ans = 0;
        for (let i = 0; i < arr.length; ++i) {
            if (arr[i] !== target[i]) {
                let j = i;
                while (arr[j] !== target[i]) j++;
                while (j > i) {
                    [arr[j], arr[j-1]] = [arr[j-1], arr[j]];
                    j--;
                    ans++;
                }
            }
        }
        return ans;
    }
}
function nextPerm(arr: string[]) {
    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]];
    }
    for (let l = i+1, r = n-1; l < r; ++l, --r) {
        [arr[l], arr[r]] = [arr[r], arr[l]];
    }
}

Complexity

  • ⏰ Time complexity: O(n*k + n^2)
    • Generating k permutations and counting swaps for each position.
  • 🧺 Space complexity: O(n)
    • For arrays.