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.
 
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.

Example 4:
Input: num = "22", k = 22
Output: "22"

Example 5:
Input: num = "9438957234785635408", k = 23
Output: "0345989723478563548"

 
Constraints:

1 <= num.length <= 30000
num contains digits only and doesn't have leading zeros.
1 <= k <= 10^9

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: String algorithms

Segment trees revisited

Range queries

Greedy algorithms

Starter code: class Solution:
    def minInteger(self, num: str, k: int) -> str:
        

Solutions:
class Solution:

	def minInteger(self, num: str, k: int) -> str:
		n = len(num)
		if k <= 0:
			return num
		if k > n * (n - 1) // 2:
			return ''.join(sorted(list(num)))
		for i in range(10):
			idx = num.find(str(i))
			if idx >= 0 and idx <= k:
				return num[idx] + self.minInteger(num[:idx] + num[idx + 1:], k - idx)


class Solution:

	def minInteger(self, num: str, k: int) -> str:
		rest = num
		move = 0
		s = ''
		for dig in range(10):
			count = 0
			digC = str(dig)
			for (i, c) in enumerate(rest):
				if c == digC:
					if k < move + i - count:
						rest = rest.replace(digC, '', count)
						s += digC * count
						remain = k - move
						mid = rest[0:remain + 1]
						while remain:
							tmp = min(mid)
							for (ti, tc) in enumerate(mid):
								if tc == tmp:
									remain -= ti
									s += tc
									rest = rest.replace(tc, '', 1)
									mid = rest[0:remain + 1]
									break
						return s + rest
					move += i - count
					count += 1
			rest = rest.replace(digC, '')
			s += digC * count
		return s


class Solution:

	def minInteger(self, num: str, k: int) -> str:
		min_num = ''.join(sorted(list(num)))
		i = 0
		to_find = 0
		while num != min_num and k > 0 and (i < len(num)):
			index = num.find(str(to_find), i)
			while index != -1:
				if index - i <= k:
					num = num[:i] + num[index] + num[i:index] + num[index + 1:]
					k -= index - i
					i += 1
					to_find = 0
					index = num.find(str(to_find), i)
				else:
					break
			to_find += 1
		return num


class Solution:

	def minInteger(self, num: str, k: int) -> str:
		n = len(num)
		if k >= (n - 1) * n // 2:
			return ''.join(sorted(num))
		ans = []
		while k and num:
			for d in '0123456789':
				i = num.find(d)
				if 0 <= i <= k:
					ans.append(d)
					num = num[:i] + num[i + 1:]
					k -= i
					break
		return ''.join(ans) + num


class Solution:

	def minInteger(self, num: str, k: int) -> str:
		if k <= 0:
			return num
		for i in range(10):
			ind = num.find(str(i))
			if 0 <= ind <= k:
				return str(num[ind]) + self.minInteger(num[0:ind] + num[ind + 1:], k - ind)
		return num


class Solution:

	def minInteger(self, num: str, k: int) -> str:
		D = 10
		ans = num
		for d in range(D):
			i = num.find(str(d))
			if i < 0:
				continue
			cost = i
			if cost > k:
				continue
			if i == 0:
				return num[i] + self.minInteger(num[i + 1:], k)
			return num[i] + self.minInteger(num[:i] + num[i + 1:], k - cost)
		return num