Minimum possible integer after at most k adjacent swaps on digits

String Greedy Binary Indexed Tree Segment Tree

41.1% acceptance

Feb 25, 2026

499

You are given a string num representing the digits of a very large integer and an integer k. You are allowed to swap any two adjacent digits of the integer at most k times. Return the minimum integer you can obtain also as a string.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn min_integer(num: String, k: i32) -> String {
    let n = num.len();
    let bytes = num.as_bytes();
    let mut k = k as usize;

    // positions[d] stores original indices of digit d in order
    let mut positions: Vec<std::collections::VecDeque<usize>> =
      vec![std::collections::VecDeque::new(); 10];
    for (i, &b) in bytes.iter().enumerate() {
      positions[(b - b'0') as usize].push_back(i);
    }

    // BIT (1-indexed) to count removed elements up to index i
    let mut bit = vec![0i32; n + 2];

    fn update(bit: &mut Vec<i32>, mut i: usize, n: usize) {
      i += 1;
      while i <= n {
        bit[i] += 1;
        i += i & i.wrapping_neg();
      }
    }

    fn query(bit: &Vec<i32>, mut i: usize) -> usize {
      i += 1;
      let mut s = 0usize;
      while i > 0 {
        s += bit[i] as usize;
        i -= i & i.wrapping_neg();
      }
      s
    }

    let mut result = Vec::with_capacity(n);

    for _ in 0..n {
      let mut found = false;
      for d in 0..10usize {
        if let Some(&orig_j) = positions[d].front() {
          // Number of elements removed before orig_j
          let removed_before = if orig_j > 0 { query(&bit, orig_j - 1) } else { 0 };
          // Cost = remaining elements before orig_j = orig_j - removed_before
          let cost = orig_j - removed_before;
          if cost <= k {
            k -= cost;
            result.push(b'0' + d as u8);
            update(&mut bit, orig_j, n);
            positions[d].pop_front();
            found = true;
            break;
          }
        }
      }
      if !found {
        // Shouldn't happen for valid input
        break;
      }
    }

    String::from_utf8(result).unwrap()
  }
}