1850. Minimum Adjacent Swaps to Reach the Kth Smallest Number

getNextPermutation: T = O(N)
getSwapCount: T = O(N^2)
T = O(k*N + N^2)

class Solution:
    def getMinSwaps(self, num: str, k: int) -> int:
        n = len(num)
        original = list(num)
        target = original[:]
        
        def getNextPermutation(num: list) -> list: 
            idx = n - 2
            while idx >= 0:
                if num[idx] < num[idx+1]:
                    break
                idx -= 1
            
            if idx == -1:
                return sorted(num)
            
            for i in range(n-1, idx, -1):
                if num[i] > num[idx]:
                    num[i], num[idx] = num[idx], num[i]
                    break
            
            left, right = idx+1, n-1
            while left < right:
                num[left], num[right] = num[right], num[left]
                left += 1
                right -= 1
            return num
        
        def getSwapCount(original: list, target: list) -> int:
            count = 0
            for i in range(n):
                if original[i] != target[i]:
                    idx = i + 1
                    while original[idx] != target[i]:
                        idx += 1
                    
                    while idx != i:
                        original[idx], original[idx-1] = original[idx-1], original[idx]
                        idx -= 1
                        count += 1
            return count
                    
        
        while k > 0:
            target = getNextPermutation(target)
            k -= 1
        
        return getSwapCount(original, target)

1850. Minimum Adjacent Swaps to Reach the Kth Smallest Number - cocoder39/coco39_LC GitHub Wiki