Minimum Adjacent Swaps to Reach the Kth Smallest Number

Minimum Adjacent Swaps to Reach the Kth Smallest Number

What is this problem about?

This multi-step problem, Minimum Adjacent Swaps to Reach the Kth Smallest Number, starts with a string representing a large number. First, you must find the "k-th next permutation" of that number (the k-th smallest number that is larger than the current one using the same digits). Then, you must calculate the minimum number of adjacent swaps needed to transform the original string into that k-th permutation.

Why is this asked in interviews?

This is a frequent Minimum Adjacent Swaps to Reach the Kth Smallest Number interview question at Meta and Google. It combines two different algorithmic concepts: the "Next Permutation" algorithm and "String Transformation Cost." It tests if a candidate can chain two separate algorithms together to solve a complex composite problem.

Algorithmic pattern used

1. Next Permutation Pattern: Use the standard algorithm (find the first decreasing element from the right, swap it with the next larger, then reverse the suffix) and repeat it k times.
2. Greedy String Matching: To find the swaps to turn string A into string B, iterate through A. For each character, find the first occurrence of the target character in the remaining part of A and "bubble" it to the current position. The number of steps it moves is the swap count.

Example explanation

Original: "142", target is 2nd next permutation.

1. Next permutations: "142" -> "214" (1st) -> "241" (2nd).
2. Transform "142" to "241":
   • Target index 0 is '2'. Find '2' in "142" (index 2).
   • Swap '2' with its neighbors until it reaches index 0: [1, 4, 2] -> [1, 2, 4] -> [2, 1, 4]. (2 swaps).
   • Target index 1 is '4'. Find '4' in current "214" (index 2).
   • Swap '4' to index 1: [2, 1, 4] -> [2, 4, 1]. (1 swap).
3. Total = 2 + 1 = 3 swaps.

Common mistakes candidates make

• Inefficient Permutation Logic: Trying to generate all permutations and sorting them, which is $O(N!)$ and will crash for long strings.
• Confusing with Inversions: Thinking the swap count is just the number of inversions. This only works if all digits are unique. If there are duplicate digits, you must use the greedy matching approach.
• Off-by-one in the loop: Errors while implementing the "Next Permutation" logic, especially in the reversal step.

Interview preparation tip

Break this problem into two clear functions: nextPermutation(string) and countSwaps(string1, string2). Interviewers love modular code. Mastering the Two Pointers interview pattern used in Next Permutation is a high-yield study goal.