1850. Minimum Adjacent Swaps to Reach the Kth Smallest Number

Medium

---

You are given a string num, representing a large integer, and an integer k.

We call some integer wonderful if it is a permutation of the digits in num and is greater in value than num. There can be many wonderful integers. However, we only care about the smallest-valued ones.

• For example, when num = "5489355142":

  <ul>
  	<li>The 1<sup>st</sup> smallest wonderful integer is <code>"5489355214"</code>.</li>
  	<li>The 2<sup>nd</sup> smallest wonderful integer is <code>"5489355241"</code>.</li>
  	<li>The 3<sup>rd</sup> smallest wonderful integer is <code>"5489355412"</code>.</li>
  	<li>The 4<sup>th</sup> smallest wonderful integer is <code>"5489355421"</code>.</li>
  </ul>
  </li>

Return the minimum number of adjacent digit swaps that needs to be applied to num to reach the kth smallest wonderful integer.

The tests are generated in such a way that kth smallest wonderful integer exists.

Example 1:

Input: num = "5489355142", k = 4
Output: 2
Explanation: The 4th smallest wonderful number is "5489355421". To get this number:
- Swap index 7 with index 8: "5489355142" -> "5489355412"
- Swap index 8 with index 9: "5489355412" -> "5489355421"

Example 2:

Input: num = "11112", k = 4
Output: 4
Explanation: The 4th smallest wonderful number is "21111". To get this number:
- Swap index 3 with index 4: "11112" -> "11121"
- Swap index 2 with index 3: "11121" -> "11211"
- Swap index 1 with index 2: "11211" -> "12111"
- Swap index 0 with index 1: "12111" -> "21111"

Example 3:

Input: num = "00123", k = 1
Output: 1
Explanation: The 1st smallest wonderful number is "00132". To get this number:
- Swap index 3 with index 4: "00123" -> "00132"

Constraints:

• 2 <= num.length <= 1000

• 1 <= k <= 1000

• num only consists of digits.

class Solution:
    def getMinSwaps(self, num: str, k: int) -> int:
        list_of_num = list(num)
        for index in range(k):
            self.nextPermutation(list_of_num)
        count = 0
        num = list(num)
        length = len(num)
        return self.numberOfSwaps(list_of_num, num)
    
    def numberOfSwaps(self, list_of_num, num) -> int:
        count = 0
        num = list(num)
        length = len(num)
        # Simply Compairing Number
        for i in range(length):
            j = i
            while j < length and list_of_num[i] != num[j]:
                j += 1
            count += j - i
            num[i:j+1] = [num[j]] + num[i:j]
        return count
    
    # Taken From Problem 31
    def nextPermutation(self, nums: List[int]) -> None:
        i = j = len(nums)-1
        while i > 0 and nums[i-1] >= nums[i]:
            i -= 1
        if i == 0:
            nums.reverse()
            return
        while nums[j] <= nums[i-1]:
            j -= 1
        nums[i-1] , nums[j] = nums[j], nums[i-1]
        left = i
        right = len(nums)-1
        while left < right:
            nums[left], nums[right] = nums[right] , nums[left]
            left += 1
            right -= 1