Minimum Possible Integer After at Most K Adjacent Swaps On Digits solution and explanation

def minInteger(num: str, k: int) -> str:
    num = list(num)
    n = len(num)
    for i in range(n):
        min_index = i
        for j in range(i + 1, min(i + k + 1, n)):
            if num[j] < num[min_index]:
                min_index = j
        k -= min_index - i
        num[i:min_index+1] = [num[min_index]] + num[i:min_index]
        if k <= 0:
            break
    return ''.join(num)

public class Solution {
    public String minInteger(String num, int k) {
        char[] chars = num.toCharArray();
        int n = chars.length;
        for (int i = 0; i < n && k > 0; i++) {
            int minIndex = i;
            for (int j = i + 1; j < n && j <= i + k; j++) {
                if (chars[j] < chars[minIndex]) {
                    minIndex = j;
                }
            }
            k -= (minIndex - i);
            char minChar = chars[minIndex];
            for (int j = minIndex; j > i; j--) {
                chars[j] = chars[j - 1];
            }
            chars[i] = minChar;
        }
        return new String(chars);
    }
}

#include <vector>
#include <string>
using namespace std;
class Solution {
    vector<int> segTree;
    int n;

    void buildTree(vector<int>& num, int left, int right, int pos) {
        if (left == right) {
            segTree[pos] = left;
            return;
        }
        int mid = (left + right) / 2;
        buildTree(num, left, mid, 2 * pos + 1);
        buildTree(num, mid + 1, right, 2 * pos + 2);
        int leftIndex = segTree[2 * pos + 1];
        int rightIndex = segTree[2 * pos + 2];
        segTree[pos] = num[leftIndex] <= num[rightIndex] ? leftIndex : rightIndex;
    }

    int query(int qlow, int qhigh, int low, int high, int pos, vector<int>& num) {
        if (qlow <= low && qhigh >= high) return segTree[pos];
        if (qlow > high || qhigh < low) return -1;
        int mid = (low + high) / 2;
        int leftIndex = query(qlow, qhigh, low, mid, 2 * pos + 1, num);
        int rightIndex = query(qlow, qhigh, mid + 1, high, 2 * pos + 2, num);
        if (leftIndex == -1) return rightIndex;
        if (rightIndex == -1) return leftIndex;
        return num[leftIndex] <= num[rightIndex] ? leftIndex : rightIndex;
    }

public:
    string minInteger(string num, int k) {
        n = num.size();
        segTree.resize(4 * n);
        vector<int> nums(n);
        for (int i = 0; i < n; ++i) nums[i] = num[i] - '0';
        buildTree(nums, 0, n - 1, 0);

        string result;
        for (int i = 0; i < n && k > 0; ++i) {
            int minIndex = query(i, min(i + k, n - 1), 0, n - 1, 0, nums);
            if (minIndex > i) {
                k -= (minIndex - i);
                result.push_back(num[minIndex]);
                nums.erase(nums.begin() + minIndex);
                segTree.clear();
                buildTree(nums, 0, n - 1, 0);
                --n;
            } else {
                result.push_back(num[i]);
            }
        }
        return result;
    }
};

class SegmentTree {
    constructor(size) {
        this.size = size;
        this.tree = Array(size * 4).fill(0);
    }

    build(nums, node, start, end) {
        if (start === end) {
            this.tree[node] = start;
        } else {
            const mid = Math.floor((start + end) / 2);
            this.build(nums, 2 * node + 1, start, mid);
            this.build(nums, 2 * node + 2, mid + 1, end);
            this.tree[node] = nums[this.tree[2 * node + 1]] <= nums[this.tree[2 * node + 2]] ? this.tree[2 * node + 1] : this.tree[2 * node + 2];
        }
    }

    query(nums, node, start, end, L, R) {
        if (R < start || L > end) {
            return -1;
        }
        if (L <= start && end <= R) {
            return this.tree[node];
        }
        const mid = Math.floor((start + end) / 2);
        const leftQuery = this.query(nums, 2 * node + 1, start, mid, L, R);
        const rightQuery = this.query(nums, 2 * node + 2, mid + 1, end, L, R);
        if (leftQuery === -1) return rightQuery;
        if (rightQuery === -1) return leftQuery;
        return nums[leftQuery] <= nums[rightQuery] ? leftQuery : rightQuery;
    }
}

function minInteger(num, k) {
    const n = num.length;
    const nums = Array.from(num).map(x => parseInt(x, 10));
    const segTree = new SegmentTree(n);
    segTree.build(nums, 0, 0, n - 1);

    let result = '';
    for (let i = 0; i < n && k > 0; i++) {
        const minIndex = segTree.query(nums, 0, 0, n - 1, i, Math.min(i + k, n - 1));
        if (minIndex > i) {
            k -= (minIndex - i);
            result += num.charAt(minIndex);
            nums.splice(minIndex, 1);
            segTree.build(nums, 0, 0, nums.length - 1);
            n--;
        } else {
            result += num.charAt(i);
        }
    }
    return result;
}

type BinaryIndexedTree struct {
	n int
	c []int
}

func newBinaryIndexedTree(n int) *BinaryIndexedTree {
	c := make([]int, n+1)
	return &BinaryIndexedTree{n, c}
}

func (this *BinaryIndexedTree) lowbit(x int) int {
	return x & -x
}

func (this *BinaryIndexedTree) update(x, delta int) {
	for x <= this.n {
		this.c[x] += delta
		x += this.lowbit(x)
	}
}

func (this *BinaryIndexedTree) query(x int) int {
	s := 0
	for x > 0 {
		s += this.c[x]
		x -= this.lowbit(x)
	}
	return s
}

func minInteger(num string, k int) string {
	pos := make([][]int, 10)
	for i, c := range num {
		pos[c-'0'] = append(pos[c-'0'], i+1)
	}
	n := len(num)
	tree := newBinaryIndexedTree(n)
	var ans strings.Builder
	for i := 1; i <= n; i++ {
		for v := 0; v < 10; v++ {
			if len(pos[v]) > 0 {
				j := pos[v][0]
				dist := tree.query(n) - tree.query(j) + j - i
				if dist <= k {
					k -= dist
					pos[v] = pos[v][1:]
					ans.WriteByte(byte(v + '0'))
					tree.update(j, 1)
					break
				}
			}
		}
	}
	return ans.String()
}