Minimum Adjacent Swaps to Reach the Kth Smallest Number
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.
Return the minimum number of adjacent digit swaps that needs to be applied to num to reach the k^th smallest wonderful integer.
The tests are generated in such a way that the k^th smallest wonderful integer exists.
Example 1
Input
num = "5489355142", k = 4Output
2The 4^th smallest wonderful number is "5489355421", which can be reached from "5489355142" with two adjacent swaps.
Example 2
Input
num = "11112", k = 4Output
4The 4^th smallest wonderful number is "21111", which requires moving the digit 2 to the front using four adjacent swaps.
Constraints
- 2 <= num.length <= 1000
- 1 <= k <= 1000
- num only consists of digits.