This problem is from LeetCode.
You're 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.
My question is, why does the following greedy algorithm work?
n <- length of num
i <- 0
while i < n and k > 0:
pos <- position of the first smallest element in num[i..min(n-1, i + k)]
while pos > i:
swap pos and pos-1 of num
decrease pos by 1
decrease k by 1
increase i by 1
The algorithm makes sense intuitively; we essentially move the minimum digit in a window of size at most k into each possible position, and since we minimize leading digits each time starting from the first leading digit, it makes intuitive sense that the resulting number should be minimized. But I'm not sure how to prove it produces an optimal solution using an exchange argument.