Skip to content

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

  • Time: $O(n\log n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
class FenwickTree {
 public:
  FenwickTree(int n) : sums(n + 1) {}

  void update(int i, int delta) {
    while (i < sums.size()) {
      sums[i] += delta;
      i += i & -i;
    }
  }

  int get(int i) {
    int sum = 0;
    while (i > 0) {
      sum += sums[i];
      i -= i & -i;
    }
    return sum;
  }

 private:
  vector<int> sums;
};

class Solution {
 public:
  string minInteger(string num, int k) {
    const int n = num.length();
    string ans;
    FenwickTree tree(n);
    vector<bool> used(n);
    vector<queue<int>> numToIndices(10);

    for (int i = 0; i < n; ++i)
      numToIndices[num[i] - '0'].push(i);

    while (k > 0 && ans.length() < n)
      for (int d = 0; d < 10; ++d) {
        if (numToIndices[d].empty())
          continue;
        const int i = numToIndices[d].front();
        const int cost = i - tree.get(i);  // note the offset 1 in FenwickTree
        if (cost > k)
          continue;
        k -= cost;
        ans += '0' + d;
        used[i] = true;
        tree.update(i + 1, 1);
        numToIndices[d].pop();
        break;  // scan from 0 -> 9 again
      }

    for (int i = 0; i < n; ++i)
      if (!used[i])
        ans += num[i];

    return ans;
  }
};