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

Return the minimum integer you can obtain also as a string.

&nbsp;
Example 1:

Input: num = "4321", k = 4
Output: "1342"
Explanation: The steps to obtain the minimum integer from 4321 with 4 adjacent swaps are shown.


Example 2:

Input: num = "100", k = 1
Output: "010"
Explanation: It's ok for the output to have leading zeros, but the input is guaranteed not to have any leading zeros.


Example 3:

Input: num = "36789", k = 1000
Output: "36789"
Explanation: We can keep the number without any swaps.


&nbsp;
Constraints:


	1 &lt;= num.length &lt;= 3 * 104
	num consists of only digits and does not contain leading zeros.
	1 &lt;= k &lt;= 109


from sortedcontainers import SortedList

class Solution:
    def minInteger(self, num: str, k: int) -> str:
        sz, window = len(num), SortedList()
        remainedIndices, poppedIndices = SortedList(range(sz)), []
        while k > 0:
            while len(window) < k + 1 and len(window) < len(remainedIndices):
                idx = remainedIndices[len(window)]
                window.add((num[idx], idx))
            if not window:
                break
            index = window.pop(0)[1]
            k -= remainedIndices.bisect_left(index)
            remainedIndices.remove(index)
            poppedIndices.append(index)
            for idx in remainedIndices[k + 1: len(window)]:
                window.remove((num[idx], idx))
        poppedSet = set(poppedIndices)
        return "".join(num[idx] for idx in poppedIndices) + "".join(num[idx] for idx in range(sz) if idx not in poppedSet)
class Solution {
    public String minInteger(String num, int k) {
        //pqs stores the location of each digit.
        List<Queue<Integer>> pqs = new ArrayList<>();
        for (int i = 0; i <= 9; ++i) {
            pqs.add(new LinkedList<>());
        }

        for (int i = 0; i < num.length(); ++i) {
            pqs.get(num.charAt(i) - '0').add(i);
        }
        String ans = "";
        SegmentTree seg = new SegmentTree(num.length());

        for (int i = 0; i < num.length(); ++i) {
            // At each location, try to place 0....9
            for (int digit = 0; digit <= 9; ++digit) {
                // is there any occurrence of digit left?
                if (pqs.get(digit).size() != 0) {
                    // yes, there is a occurrence of digit at pos
                    Integer pos = pqs.get(digit).peek();
					// Since few numbers already shifted to left, this `pos` might be outdated.
                    // we try to find how many number already got shifted that were to the left of pos.
                    int shift = seg.getCountLessThan(pos);
                    // (pos - shift) is number of steps to make digit move from pos to i.
                    if (pos - shift <= k) {
                        k -= pos - shift;
                        seg.add(pos); // Add pos to our segment tree.
                        pqs.get(digit).remove();
                        ans += digit;
                        break;
                    }
                }
            }
        }
        return ans;
    }

    class SegmentTree {
        int[] nodes;
        int n;

        public SegmentTree(int max) {
            nodes = new int[4 * (max)];
            n = max;
        }

        public void add(int num) {
            addUtil(num, 0, n, 0);
        }

        private void addUtil(int num, int l, int r, int node) {
            if (num < l || num > r) {
                return;
            }
            if (l == r) {
                nodes[node]++;
                return;
            }
            int mid = (l + r) / 2;
            addUtil(num, l, mid, 2 * node + 1);
            addUtil(num, mid + 1, r, 2 * node + 2);
            nodes[node] = nodes[2 * node + 1] + nodes[2 * node + 2];
        }

        // Essentialy it tells count of numbers < num.
        public int getCountLessThan(int num) {
            return getUtil(0, num, 0, n, 0);
        }

        private int getUtil(int ql, int qr, int l, int r, int node) {
            if (qr < l || ql > r) return 0;
            if (ql <= l && qr >= r) {
                return nodes[node];
            }

            int mid = (l + r) / 2;
            return getUtil(ql, qr, l, mid, 2 * node + 1) + getUtil(ql, qr, mid + 1, r, 2 * node + 2);
        }
    }

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

class SegmentTree {
    vector<int> tree;

public:
    SegmentTree(int size) {
        tree.resize(4 * size + 1, 0);
    }

    void printTree() {
        for (int num : tree) cout << num << "";
        cout << endl;
    }

    void updateTree(int lo, int hi, int index, int upd) {
        if (upd < lo || upd > hi) return;
        if (lo == hi) {
            tree[index]++;
            return;
        }
        int mid = lo + (hi - lo) / 2;
        updateTree(lo, mid, 2 * index, upd);
        updateTree(mid + 1, hi, 2 * index + 1, upd);
        tree[index] = tree[2 * index] + tree[2 * index + 1];
    }

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

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

        int left = queryTree(lo, mid, 2 * index, qs, qe);
        int right = queryTree(mid + 1, hi, 2 * index + 1, qs, qe);
        return left + right;
    }
};

class Solution {
public:
    string minInteger(string num, int k) {
        queue<int> pos[10];
        for (int i = 0; i < num.length(); i++) {
            pos[num[i] - '0'].push(i);
        }
        string res = "";
        SegmentTree *seg = new SegmentTree((int)num.length());
        for (int i = 0; i < num.length(); i++) {
            if (num[i] == '-') continue;
            int digit = num[i] - '0';

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

                    if (curNumIndex - i - shifts <= k) {
                        seg->updateTree(0, num.length() - 1, 1, curNumIndex);
                        k -= curNumIndex - i - shifts;
                        pos[j].pop();
                        res += num[curNumIndex];
                        num[curNumIndex] = '-';
                        swapped = true;
                        i--;
                        break;
                    }
                }
            }
            if (!swapped) {
                res += num[i];
                pos[digit].pop();
            }
        }
        return res;
    }
};
/**
 * @param {string} num
 * @param {number} k
 * @return {string}
 
 Idea is based on bubble sorting with limited steps k
 
 */

var minInteger = function(num, k) {
    if (num.length == 1)
        return num;
    
    let nums = num.split('');
    let i = 0, j = 0;
    
    while (k && i < num.length-1) {
//         step 0: if leading zero, check the next digit
        if (nums[i] == '0') {
            i++;
            j++;
            continue;
        }
        
//         step 1: find the min digit 
        let p = j, steps = 0;
        while (nums[p] !== '0' && j < nums.length && steps <= k) {
            if (nums[j] < nums[p])
                p = j;
            j++;
            steps++;
        }
        
//         step 2: nums[i] is the current minimum digit --> check next digit
        if (p == i) {
            i++;
            j = i;
            continue;
        }
            
//          step 3: move the min digit to i
        for (; p > i; p--) {
            [nums[p], nums[p-1]] = [nums[p-1], nums[p]];
            k--;
        }
        
        i++;
        j = i;
        
    }
    
    return nums.join('');
};
Minimum Possible Integer After at Most K Adjacent Swaps On Digits