1505. Minimum Possible Integer After at Most K Adjacent Swaps On Digits

Description

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.

 

Example 1:

Input: num = "4321", k = 4
Output: "1342"
Explanation: The steps to obtain the minimum integer from 4321 with 4 adjacent swaps are shown.

Example 2:

Input: num = "100", k = 1
Output: "010"
Explanation: It's ok for the output to have leading zeros, but the input is guaranteed not to have any leading zeros.

Example 3:

Input: num = "36789", k = 1000
Output: "36789"
Explanation: We can keep the number without any swaps.

 

Constraints:

• 1 <= num.length <= 3 * 104
• num consists of only digits and does not contain leading zeros.
• 1 <= k <= 109

 

Solutions

Solution: Greedy + Binary Indexed Tree

• Time complexity: O(nlogn)
• Space complexity: O(n)

 

JavaScript

/**
 * @param {string} num
 * @param {number} k
 * @return {string}
 */
const minInteger = function (num, k) {
  const n = num.length;
  const tree = new BinaryIndexedTree(n);
  const used = new Array(n + 1).fill(false);
  const numIndices = Array.from({ length: 10 }, () => []);
  let result = '';

  for (let index = 0; index < n; index++) {
    numIndices[Number(num[index])].push(index);
  }

  while (result.length < n && k) {
    for (let digit = 0; digit < 10; digit++) {
      if (!numIndices[digit].length) continue;
      const index = numIndices[digit][0];
      const cost = index - tree.get(index);

      if (cost > k) continue;

      k -= cost;
      result += digit;
      tree.add(index + 1, 1);
      used[index] = true;
      numIndices[digit].shift();
      break;
    }
  }

  for (let index = 0; index < n; index++) {
    if (used[index]) continue;

    result += num[index];
  }

  return result;
};

class BinaryIndexedTree {
  constructor(n) {
    this.sums = new Array(n + 1).fill(0);
  }

  add(index, delta) {
    while (index < this.sums.length) {
      this.sums[index] += delta;
      index += index & -index;
    }
  }

  get(index) {
    let sum = 0;

    while (index > 0) {
      sum += this.sums[index];
      index -= index & -index;
    }

    return sum;
  }
}