1850. Minimum Adjacent Swaps to Reach the Kth Smallest Number

Problem Link

Description

---

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>&quot;5489355214&quot;</code>.</li>
  	<li>The 2<sup>nd</sup> smallest wonderful integer is <code>&quot;5489355241&quot;</code>.</li>
  	<li>The 3<sup>rd</sup> smallest wonderful integer is <code>&quot;5489355412&quot;</code>.</li>
  	<li>The 4<sup>th</sup> smallest wonderful integer is <code>&quot;5489355421&quot;</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.

Solution

---

Python3

class Solution:
    def getMinSwaps(self, nums: str, k: int) -> int:
        n = len(nums)
        
        def nextPermutation(nums):
            i = n - 1
            while i > 0 and nums[i-1] >= nums[i]:
                i -= 1
                
            j = i
            while j < n and nums[i-1] < nums[j]:
                j += 1
                
            nums[i-1], nums[j-1] = nums[j-1], nums[i-1]
            nums[i:] = nums[i:][::-1]
            
            return nums
        
        swapped = list(nums)
        for _ in range(k):
            swapped = nextPermutation(swapped)
        
        res = 0
        for i in range(n):
            j = i
            
            while j < n and swapped[j] != nums[i]: j += 1
            
            while i < j:
                swapped[j], swapped[j - 1] = swapped[j - 1], swapped[j]
                res += 1
                j -= 1
        
        return res