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

Difficulty: interview

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:
        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)
        
        
        
        
        
        
        '''from collections import deque
        j=0
        
        arr=[deque() for i in range(10)]
        
        n=len(num)
        
        for i in range(n):
            arr[int(num[i])].append(i)
            #print(arr)
        
        curr=0
        ans=\"\"
        
        def fun(x,y):
            l=list(arr[x])
            l.append(y)
            l.sort()
            arr[x]=deque(l)
        
        while k>0 and curr<n:
            ch=None
            ch_ind=curr
            for i in range(0,int(num[curr])):
                if arr[i] and arr[i][0]<=k:
                    ch=i
                    ch_ind=arr[i][0]
                    arr[i].popleft()
                    break
                    
            print(arr,ch,ch_ind,curr,k)
            if ch:
                ans+=str(ch)
                k-=(ch_ind-curr)
                
            else:
                ans+=num[curr]
                curr+=1
            print(ans)
            
        
        return ans'''

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:
        if k == 0: return num 
        n = len(num)
        if k >= n*(n+1)//2: return ''.join(sorted(num))
        for i in range(10):
            idx = num.find(str(i))
            if 0<=idx<=k:
                res = str(i) + self.minInteger(num[:idx]+num[idx+1:], k-idx)
                return res 

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:
    ''' greedy approach. start from the left side, 
\t    and everytime pick the smallest number on the right side that is able to swap, then do the swap
    '''
    def minInteger(self, num: str, k: int) -> str:
        min_num = sorted(list(num))
        min_num = ''.join(min_num)
        i = 0
        to_find = 0
        while num != min_num and k > 0 and i < len(num):
            indx = num.find(str(to_find), i)
            while indx != -1:
                if indx - i <= k:   # able to swap
                    num = num[:i] + num[indx] + num[i:indx] + num[indx+1:]  # the swap
                    k -= (indx - i)
                    i += 1
                    to_find = 0     # restart the to_find variable
                    indx = 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:
        n = len(num)
        if k <= 0:
            return num
        if k >= (n+1)*n//2:
            return ''.join(sorted(num))
        
        for i in range(10):
            index = num.find(str(i))
            if 0 <= index <= k:
                return str(num[index]) + self.minInteger(num[:index]+num[index+1:], k-index)
            
        return 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