Minimum adjacent swaps to reach the kth smallest number

Two Pointers String Greedy

72.1% acceptance

Feb 25, 2026

808

120

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. Return the minimum number of adjacent digit swaps that needs to be applied to num to reach the kth smallest wonderful integer.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn get_min_swaps(num: String, k: i32) -> i32 {
    let original: Vec<u8> = num.bytes().collect();
    let mut target = original.clone();

    // Apply next_permutation k times
    for _ in 0..k {
      next_permutation(&mut target);
    }

    // Count adjacent swaps needed: for each position, bring target[i] from current array
    let n = original.len();
    let mut cur = original.clone();
    let mut swaps = 0i32;

    for i in 0..n {
      // Find target[i] in cur starting from i
      let mut j = i;
      while j < n && cur[j] != target[i] {
        j += 1;
      }
      // Bubble cur[j] left to position i
      while j > i {
        cur.swap(j, j - 1);
        j -= 1;
        swaps += 1;
      }
    }

    swaps
  }
}

fn next_permutation(digits: &mut Vec<u8>) {
  let n = digits.len();
  // Find rightmost i where digits[i] < digits[i+1]
  let i = match (0..n - 1).rev().find(|&i| digits[i] < digits[i + 1]) {
    Some(i) => i,
    None => {
      digits.reverse();
      return;
    }
  };
  // Find rightmost j where digits[j] > digits[i]
  let j = (i + 1..n).rev().find(|&j| digits[j] > digits[i]).unwrap();
  digits.swap(i, j);
  digits[i + 1..].reverse();
}