<p>You are given a string <code>num</code> representing <strong>the digits</strong> of a very large integer and an integer <code>k</code>. You are allowed to swap any two adjacent digits of the integer <strong>at most</strong> <code>k</code> times.</p>

<p>Return <em>the minimum integer you can obtain also as a string</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/06/17/q4_1.jpg" style="width: 500px; height: 40px;" />
<pre>
<strong>Input:</strong> num = &quot;4321&quot;, k = 4
<strong>Output:</strong> &quot;1342&quot;
<strong>Explanation:</strong> The steps to obtain the minimum integer from 4321 with 4 adjacent swaps are shown.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> num = &quot;100&quot;, k = 1
<strong>Output:</strong> &quot;010&quot;
<strong>Explanation:</strong> It&#39;s ok for the output to have leading zeros, but the input is guaranteed not to have any leading zeros.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> num = &quot;36789&quot;, k = 1000
<strong>Output:</strong> &quot;36789&quot;
<strong>Explanation:</strong> We can keep the number without any swaps.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= num.length &lt;= 3 * 10<sup>4</sup></code></li>
	<li><code>num</code> consists of only <strong>digits</strong> and does not contain <strong>leading zeros</strong>.</li>
	<li><code>1 &lt;= k &lt;= 10<sup>9</sup></code></li>
</ul>

class Solution {
public:
    struct fenwick {
        int n;
        vector<int> b;
        fenwick(int n) : n(n), b(n, 0) {}
        int lowbit(int x) { return x & (-x); }
        void update(int p, int d) {
            while (p <= n) {
                b[p] += d;
                p += lowbit(p);
            }
        }
        int get(int p) {
            int s = 0;
            while (p > 0) {
                s += b[p];
                p -= lowbit(p);
            }
            return s;
        }
    };
    string minInteger(string num, int k) {
        int n = num.size();
        // fenwick tree with size n*2
        stack<int> pos[10];
        for (int i = n; i > 0; i--) {
            pos[num[i - 1] - '0'].push(i);
        }
        fenwick f(2 * n + 1);
        for (int i = n + 1; i <= 2 * n; i++) {
            f.update(i, 1);
        }
        auto real = [&](int o) { return f.get(o + n); };
        string ans;
        for (int i = 1; i <= n; i++) {
            int curChar;
            for (curChar = 0; curChar <= 9; curChar++) {
                if (!pos[curChar].empty() && real(pos[curChar].top()) == i) {
                    break;
                }
            }
            // smallest
            int p = -1;
            int x;
            for (x = 0; x < curChar; x++) {
                if (!pos[x].empty() && real(pos[x].top()) - i <= k) {
                    p = pos[x].top();
                    pos[x].pop();
                    break;
                }
            }
            if (p != -1) {
                k -= (real(p) - i);
                f.update(i, 1);
                f.update(n + p, -1);
                ans.push_back(x + '0');
            } else {
                f.update(i, 1);
                f.update(n + pos[curChar].top(), -1);
                pos[curChar].pop();
                ans.push_back(curChar + '0');
            }

        }
        return ans;
    }
};
12600