Description#
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.
Return the minimum number of adjacent digit swaps that needs to be applied to num to reach the kth smallest wonderful integer.
The tests are generated in such a way that kth smallest wonderful integer exists.
Example 1:
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: "5489355142" -> "5489355412"
- Swap index 8 with index 9: "5489355412" -> "5489355421"
Example 2:
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: "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 1st smallest wonderful number is "00132". To get this number:
- Swap index 3 with index 4: "00123" -> "00132"
Constraints:
2 <= num.length <= 10001 <= k <= 1000num only consists of digits.
Solutions#
Solution 1: Find Next Permutation + Inversion Pairs#
We can call the next_permutation function $k$ times to get the $k$th smallest permutation $s$.
Next, we just need to calculate how many swaps are needed for $num$ to become $s$.
Let’s first consider a simple situation where all the digits in $num$ are different. In this case, we can directly map the digit characters in $num$ to indices. For example, if $num$ is "54893" and $s$ is "98345". We map each digit in $num$ to an index, that is:
$$
\begin{aligned}
num[0] &= 5 &\rightarrow& \quad 0 \
num[1] &= 4 &\rightarrow& \quad 1 \
num[2] &= 8 &\rightarrow& \quad 2 \
num[3] &= 9 &\rightarrow& \quad 3 \
num[4] &= 3 &\rightarrow& \quad 4 \
\end{aligned}
$$
Then, mapping each digit in $s$ to an index results in "32410". In this way, the number of swaps needed to change $num$ to $s$ is equal to the number of inversion pairs in the index array after $s$ is mapped.
If there are identical digits in $num$, we can use an array $d$ to record the indices where each digit appears, where $d[i]$ represents the list of indices where the digit $i$ appears. To minimize the number of swaps, when mapping $s$ to an index array, we only need to greedily select the index of the corresponding digit in $d$ in order.
Finally, we can directly use a double loop to calculate the number of inversion pairs, or we can optimize it with a Binary Indexed Tree.
The time complexity is $O(n \times (k + n))$, and the space complexity is $O(n)$. Where $n$ is the length of $num$.
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
| class Solution:
def getMinSwaps(self, num: str, k: int) -> int:
def next_permutation(nums: List[str]) -> bool:
n = len(nums)
i = n - 2
while i >= 0 and nums[i] >= nums[i + 1]:
i -= 1
if i < 0:
return False
j = n - 1
while j >= 0 and nums[j] <= nums[i]:
j -= 1
nums[i], nums[j] = nums[j], nums[i]
nums[i + 1 : n] = nums[i + 1 : n][::-1]
return True
s = list(num)
for _ in range(k):
next_permutation(s)
d = [[] for _ in range(10)]
idx = [0] * 10
n = len(s)
for i, c in enumerate(num):
j = ord(c) - ord("0")
d[j].append(i)
arr = [0] * n
for i, c in enumerate(s):
j = ord(c) - ord("0")
arr[i] = d[j][idx[j]]
idx[j] += 1
return sum(arr[j] > arr[i] for i in range(n) for j in range(i))
|
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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
| class Solution {
public int getMinSwaps(String num, int k) {
char[] s = num.toCharArray();
for (int i = 0; i < k; ++i) {
nextPermutation(s);
}
List<Integer>[] d = new List[10];
Arrays.setAll(d, i -> new ArrayList<>());
int n = s.length;
for (int i = 0; i < n; ++i) {
d[num.charAt(i) - '0'].add(i);
}
int[] idx = new int[10];
int[] arr = new int[n];
for (int i = 0; i < n; ++i) {
arr[i] = d[s[i] - '0'].get(idx[s[i] - '0']++);
}
int ans = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < i; ++j) {
if (arr[j] > arr[i]) {
++ans;
}
}
}
return ans;
}
private boolean nextPermutation(char[] nums) {
int n = nums.length;
int i = n - 2;
while (i >= 0 && nums[i] >= nums[i + 1]) {
--i;
}
if (i < 0) {
return false;
}
int j = n - 1;
while (j >= 0 && nums[i] >= nums[j]) {
--j;
}
swap(nums, i++, j);
for (j = n - 1; i < j; ++i, --j) {
swap(nums, i, j);
}
return true;
}
private void swap(char[] nums, int i, int j) {
char t = nums[i];
nums[i] = nums[j];
nums[j] = t;
}
}
|
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
| class Solution {
public:
int getMinSwaps(string num, int k) {
string s = num;
for (int i = 0; i < k; ++i) {
next_permutation(begin(s), end(num));
}
vector<int> d[10];
int n = num.size();
for (int i = 0; i < n; ++i) {
d[num[i] - '0'].push_back(i);
}
int idx[10]{};
vector<int> arr(n);
for (int i = 0; i < n; ++i) {
arr[i] = d[s[i] - '0'][idx[s[i] - '0']++];
}
int ans = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < i; ++j) {
if (arr[j] > arr[i]) {
++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
35
36
37
38
39
40
41
42
43
44
45
46
47
| func getMinSwaps(num string, k int) (ans int) {
s := []byte(num)
for ; k > 0; k-- {
nextPermutation(s)
}
d := [10][]int{}
for i, c := range num {
j := int(c - '0')
d[j] = append(d[j], i)
}
idx := [10]int{}
n := len(s)
arr := make([]int, n)
for i, c := range s {
j := int(c - '0')
arr[i] = d[j][idx[j]]
idx[j]++
}
for i := 0; i < n; i++ {
for j := 0; j < i; j++ {
if arr[j] > arr[i] {
ans++
}
}
}
return
}
func nextPermutation(nums []byte) bool {
n := len(nums)
i := n - 2
for i >= 0 && nums[i] >= nums[i+1] {
i--
}
if i < 0 {
return false
}
j := n - 1
for j >= 0 && nums[j] <= nums[i] {
j--
}
nums[i], nums[j] = nums[j], nums[i]
for i, j = i+1, n-1; i < j; i, j = i+1, j-1 {
nums[i], nums[j] = nums[j], nums[i]
}
return true
}
|
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
40
41
42
43
44
45
| function getMinSwaps(num: string, k: number): number {
const n = num.length;
const s = num.split('');
for (let i = 0; i < k; ++i) {
nextPermutation(s);
}
const d: number[][] = Array.from({ length: 10 }, () => []);
for (let i = 0; i < n; ++i) {
d[+num[i]].push(i);
}
const idx: number[] = Array(10).fill(0);
const arr: number[] = [];
for (let i = 0; i < n; ++i) {
arr.push(d[+s[i]][idx[+s[i]]++]);
}
let ans = 0;
for (let i = 0; i < n; ++i) {
for (let j = 0; j < i; ++j) {
if (arr[j] > arr[i]) {
ans++;
}
}
}
return ans;
}
function nextPermutation(nums: string[]): boolean {
const n = nums.length;
let i = n - 2;
while (i >= 0 && nums[i] >= nums[i + 1]) {
i--;
}
if (i < 0) {
return false;
}
let j = n - 1;
while (j >= 0 && nums[i] >= nums[j]) {
j--;
}
[nums[i], nums[j]] = [nums[j], nums[i]];
for (i = i + 1, j = n - 1; i < j; ++i, --j) {
[nums[i], nums[j]] = [nums[j], nums[i]];
}
return true;
}
|
