Formatted question description: https://leetcode.ca/all/1850.html
1850. Minimum Adjacent Swaps to Reach the Kth Smallest Number
Level
Medium
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.
- 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"
.
- The 1st smallest wonderful integer is
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 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 <= 1000
1 <= k <= 1000
num
only consists of digits.
Solution
Repeat k
times to find the next permutation of num
. Use original
and swapped
to represent the original string s
and the k
-th smallest number. Then use a greedy approach. Loop over original
and swapped
. If there exists an index i
such that swapped[i] != original[i]
, then find the minimum index j
such that swapped[i] == original[j]
and move original[j]
to original[i]
. Calculate the number of swaps during the process. Finally, return the number of swaps.
class Solution {
public int getMinSwaps(String num, int k) {
int minSwaps = 0;
char[] swapped = num.toCharArray();
for (int i = 1; i <= k; i++)
nextPermutation(swapped);
char[] original = num.toCharArray();
int length = original.length;
for (int i = 0; i < length; i++) {
if (swapped[i] != original[i]) {
for (int j = i + 1; j < length; j++) {
if (swapped[i] == original[j]) {
for (int m = j - 1; m >= i; m--) {
original[m + 1] = original[m];
minSwaps++;
}
original[i] = swapped[i];
break;
}
}
}
}
return minSwaps;
}
public void nextPermutation(char[] array) {
int i = array.length - 2;
while (i >= 0 && array[i] >= array[i + 1])
i--;
if (i >= 0) {
int j = array.length - 1;
while (j >= 0 && array[i] >= array[j])
j--;
swap(array, i, j);
}
reverse(array, i + 1);
}
public void swap(char[] array, int i, int j) {
char temp = array[i];
array[i] = array[j];
array[j] = temp;
}
public void reverse(char[] array, int start) {
int left = start, right = array.length - 1;
while (left < right) {
swap(array, left, right);
left++;
right--;
}
}
}