<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:
    class SegTree:
        def __init__(self, n):
            self.n = n
            self.cnt = [0] * (n * 4)

        def add(self,idx):
            self._add(idx, 0, self.n - 1, 0)

        def _add(self, idx, l, r, node):
            if (idx < l) or (idx > r):
                return
            self.cnt[node] += 1
            if (l == r):
                return
            mid = (l + r) // 2
            self._add(idx, l, mid, 2 * node + 1)
            self._add(idx, mid + 1, r, 2 * node + 2)
        
        def query(self, ql, qr):
            return self._query(ql, qr, 0, self.n - 1, 0)
        
        def _query(self, ql, qr, l, r, node):
            if (ql > r) or (qr < l):
                return 0
            if (ql <= l) and (qr >= r):
                return self.cnt[node]
            mid = (l + r) // 2
            ret = self._query(ql, qr, l, mid, node * 2 + 1)
            ret += self._query(ql, qr, mid + 1, r, node * 2 + 2)
            return ret

    def minInteger(self, num: str, k: int) -> str:
        n = len(num)
        num2idx = [[] for x in range(10)]
        for i, x in enumerate(num):
            num2idx[ord(x) - ord('0')].append(i)
        first = [0] * 10
        seg = self.SegTree(n)

        ret = ''
        i = 0
        for j in range(n):
            for x in range(10):
                if first[x] < len(num2idx[x]):
                    idx = num2idx[x][first[x]]
                    step = idx - i - seg.query(i, idx) 
                    if step <= k:
                        k -= step
                        first[x] += 1
                        ret = ret + chr(x + ord('0'))
                        seg.add(idx)
                        if i == idx:
                            i = n
                            for x in range(10):
                                if first[x] < len(num2idx[x]):
                                    i = min(num2idx[x][first[x]], i)
                        break
        return ret

20100