Logo
IconChallenge
Icon
IconProblem
IconSolutions
IconSubmissions

Minimum Adjacent Swaps to Reach the Kth Smallest Number

XPChallenge Points: 20
levelLevel: Medium

You are given a number num in string format and an integer k.
Consider all permutations of the digits of num that are greater than num.
Among those, we are only interested in the k-th smallest permutation based on numerical order.

Once we determine that k-th smallest permutation, you must convert the original number num into that permutation, but you are only allowed to swap two adjacent digits at a time.

Your task is to return the minimum number of adjacent swaps required to transform num into the k-th smallest greater permutation.

It is guaranteed that the k-th permutation exists.

Example 1:

Input: num = "2765", k = 1

Output: 1

Explanation:

Next greater permutation is "2 7 6 5" -> "2 7 5 6". Swapping positions 2 and 3 gives "2756".

Example 2:

Input: num = "12354", k = 2

Output: 3

Explanation:

1st next: "12435" 2nd next: "12453" Transform "12354" → "12453" by 3 adjacent swaps.

Example 3:

Input: num = "909", k = 1

Output: 1

Explanation:

Next greater arrangement is "990". Only one adjacent swap needed.

to Continue
like
dislike

Accepted:

Submission:

IconReport an issue
Icon
IconCode
IconYou need toto run or submitYou need toto run or submit
IconTest Case
IconTest Result