Minimum Adjacent Swaps to Reach the Kth Smallest Number
MediumUpdated: Aug 2, 2025
Practice on:
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".
- The 1st smallest wonderful integer is
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
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
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
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 <= 10001 <= k <= 1000numonly 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
- Convert the string to a list of digits.
- Generate the next permutation k times to get the target permutation.
- 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.
- Repeat for all positions.
- Return the total swap count.
Code
C++
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;
}
};
Go
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]
}
}
Java
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;
}
}
}
Kotlin
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--
}
}
}
Python
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
Rust
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
}
}
TypeScript
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.