Minimum Possible Integer After at Most K Adjacent Swaps On Digits LeetCode solution in C++

1
/*
2
    Time: O(nlogn)
3
    Space: O(n)
4
    Tag: Segment Tree, Greedy (put the possible feasible smallest index in place
5
   of cur index), Queue Difficulty: H (Both Logic and Implementation)
6
*/
7

8
class SegmentTree {
9
  vector<int> tree;
10

11
 public:
12
  SegmentTree(int size) {
13
    tree.resize(4 * size + 1, 0);
14
  }
15

16
  void printTree() {
17
    for (int num : tree) cout << num << "";
18
    cout << endl;
19
  }
20

21
  void updateTree(int lo, int hi, int index, int upd) {
22
    if (upd < lo || upd > hi) return;
23
    if (lo == hi) {
24
      tree[index]++;
25
      return;
26
    }
27
    int mid = lo + (hi - lo) / 2;
28
    updateTree(lo, mid, 2 * index, upd);
29
    updateTree(mid + 1, hi, 2 * index + 1, upd);
30
    tree[index] = tree[2 * index] + tree[2 * index + 1];
31
  }
32

33
  int queryTree(int lo, int hi, int index, int qs, int qe) {
34
    if (qe < lo || qs > hi) return 0;
35
    if (qe >= hi && qs <= lo) return tree[index];
36

37
    int mid = lo + (hi - lo) / 2;
38

39
    int left = queryTree(lo, mid, 2 * index, qs, qe);
40
    int right = queryTree(mid + 1, hi, 2 * index + 1, qs, qe);
41
    return left + right;
42
  }
43
};
44

45
class Solution {
46
 public:
47
  string minInteger(string num, int k) {
48
    queue<int> pos[10];
49
    for (int i = 0; i < num.length(); i++) {
50
      pos[num[i] - '0'].push(i);
51
    }
52
    string res = "";
53
    SegmentTree *seg = new SegmentTree((int)num.length());
54
    for (int i = 0; i < num.length(); i++) {
55
      if (num[i] == '-') continue;
56
      int digit = num[i] - '0';
57

58
      bool swapped = false;
59
      for (int j = 0; j < digit; j++) {
60
        if (pos[j].size() > 0) {
61
          int curNumIndex = pos[j].front();
62
          int shifts = seg->queryTree(0, num.length() - 1, 1, i, pos[j].front());
63

64
          if (curNumIndex - i - shifts <= k) {
65
            seg->updateTree(0, num.length() - 1, 1, curNumIndex);
66
            k -= curNumIndex - i - shifts;
67
            pos[j].pop();
68
            res += num[curNumIndex];
69
            num[curNumIndex] = '-';
70
            swapped = true;
71
            i--;
72
            break;
73
          }
74
        }
75
      }
76
      if (!swapped) {
77
        res += num[i];
78
        pos[digit].pop();
79
      }
80
    }
81
    return res;
82
  }
83
};