<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:
    def minInteger(self, num: str, k: int) -> str:
        # Make a priority queue for each digit and push all occurances
        digit_queue = [deque() for _ in range(10)]
        for i, n in enumerate(num):
            digit_queue[int(n)].append(i)
        print(digit_queue)
        
        # Select next lowest in queue that satifies k constraint
        # Need to keep track of swapped indicies with segment tree to properly count # of swaps required
        seg_tree = SegmentTree(len(num))
        new_num = []
        swapped_indicies = set()
        for _ in range(len(num)):
            for digit in range(10):
                if len(digit_queue[digit]) > 0:
                    swap_index = digit_queue[digit][0]
                    shift = seg_tree.get_count_less_than(swap_index)
                    print(swap_index, shift, k)
                    if swap_index - shift <= k:
                        # swapped_indicies.add(swap_index)
                        new_num.append(str(digit))
                        seg_tree.add(swap_index)
                        k -= digit_queue[digit][0] - shift
                        digit_queue[digit].popleft()
                        break

        # for i, n in enumerate(num):
        #     if i not in swapped_indicies:
        #         new_num.append(n)

        
        return ''.join(new_num)


class SegmentTree:

    def __init__(self, size):
        self.nodes = [0] * (4 * size)
        self.n = size
    
    def add(self, num):
        self.add_dfs(num, 0, self.n, 0)
    
    # Takes num to add, left and right range pointers, and current node location
    def add_dfs(self, num, left, right, node):
        # Out of range
        if right < num or left > num:
            return
        # Leaf node
        if left == right:
            self.nodes[node] += 1
            return
        # Recurse down left and right subtree
        mid = left + (right - left) // 2
        self.add_dfs(num, left, mid, 2 * node + 1)
        self.add_dfs(num, mid + 1, right, 2 * node + 2)
        self.nodes[node] = self.nodes[2 * node + 1] + self.nodes[2 * node + 2]
    
    def get_count_less_than(self, num):
        return self.get_dfs(0, num, 0, self.n, 0)
    
    # Takes query endpoints, range endpoints, and current node location
    def get_dfs(self, query_left, query_right, left, right, node):
        # Out of range
        if left > query_right or right < query_left:
            return 0
        # Within range
        if left >= query_left and right <= query_right:
            return self.nodes[node]
        mid = left + (right - left) // 2
        left_subtree = self.get_dfs(query_left, query_right, left, mid, 2 * node + 1)
        right_subtree = self.get_dfs(query_left, query_right, mid + 1, right, 2 * node + 2)
        return left_subtree + right_subtree
    
    
21100