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.
num = "5489355142":
"5489355214"."5489355241"."5489355412"."5489355421".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 <= 10001 <= k <= 1000num only consists of digits.Problem Overview: Given a numeric string num and an integer k, find the minimum number of adjacent swaps required to transform num into its kth next lexicographically smallest permutation. You first determine what the kth permutation looks like, then compute how many adjacent swaps are needed to reach it.
Approach 1: Using Next Permutation (O(k·n + n²) time, O(n) space)
Generate the target number by applying the next_permutation operation k times on the original string. This algorithm scans from right to left to find the first decreasing pair, swaps with the next larger digit, then reverses the suffix. Once the kth permutation is obtained, compute the minimum adjacent swaps needed to convert the original string into this target. Iterate through each position; when digits differ, search forward in the target and repeatedly swap left until the correct digit reaches the position. This simulates the minimum adjacent swaps required. The approach relies on string manipulation and a greedy bubble-style swap process.
Approach 2: Optimized Swap Calculation (O(k·n + n²) time, O(1) extra space)
After generating the kth permutation, compute swaps more efficiently using a greedy shifting strategy. Traverse both strings from left to right. If characters match, move forward. When they differ, locate the matching digit in the target suffix, then shift it left using adjacent swaps while counting operations. Each shift reduces the distance between the digit's current index and its desired position. This guarantees the minimal number of swaps because adjacent swaps preserve relative ordering. The logic combines ideas from greedy algorithms with pointer scanning similar to two pointers.
Recommended for interviews: Interviewers typically expect the next permutation approach combined with a greedy adjacent swap count. Showing the next_permutation logic demonstrates understanding of permutation generation, while the swap simulation shows how to compute minimal adjacent operations. The optimized swap counting variant is cleaner in implementation and easier to reason about during interviews.
This approach involves finding the next permutation of the given number sequentially k times. Once we have the kth permutation, we compare it with the original number and calculate the minimum swaps needed to transform the original number into this new permutation.
This Python function first computes the kth permutation by finding the next permutation k times. The next_permutation function rearranges the list into the next lexicographically greater permutation. After obtaining the kth permutation, we calculate the minimum swaps needed to transform the original permutation into the kth one. This is achieved by finding the index of the element in the current list that matches the desired permutation and swapping it into the correct place.
Python
JavaScript
Time Complexity: O(n * k), where n is the length of the string and k is the number of permutations to find.
Space Complexity: O(n), for storing the list representation of the numbers.
This approach involves computing the kth permutation more efficiently using an algorithm to apply the minimum adjacent swaps directly based on the differences between current and target permutations. Instead of finding all permutations, this focuses on achieving the next permutations and dynamically swaps to approach the target.
This C++ implementation leverages the STL next_permutation to determine the kth permutation, then efficiently finds the number of adjacent swaps needed to reach this permutation. It does so by comparing the original and target permutations, only rearranging elements when necessary, and counting the swaps required for transformations.
Time Complexity: O(n * k), where obtaining the next permutation takes O(n) for each of the k iterations.
Space Complexity: O(n), due to additional space needed for swap vectors or temporary strings.
We can call the next_permutation function k times to get the kth smallest permutation s.
Next, we just need to calculate how many swaps are needed for num to become s.
Let's first consider a simple situation where all the digits in num are different. In this case, we can directly map the digit characters in num to indices. For example, if num is "54893" and s is "98345". We map each digit in num to an index, that is:
$
\begin{aligned}
num[0] &= 5 &\rightarrow& \quad 0 \
num[1] &= 4 &\rightarrow& \quad 1 \
num[2] &= 8 &\rightarrow& \quad 2 \
num[3] &= 9 &\rightarrow& \quad 3 \
num[4] &= 3 &\rightarrow& \quad 4 \
\end{aligned}
Then, mapping each digit in s to an index results in num"32410". In this way, the number of swaps needed to change to s is equal to the number of inversion pairs in the index array after s is mapped.
If there are identical digits in num, we can use an array d to record the indices where each digit appears, where d[i] represents the list of indices where the digit i appears. To minimize the number of swaps, when mapping s to an index array, we only need to greedily select the index of the corresponding digit in d in order.
Finally, we can directly use a double loop to calculate the number of inversion pairs, or we can optimize it with a Binary Indexed Tree.
The time complexity is O(n times (k + n)), and the space complexity is O(n). Where n is the length of num$.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Approach 1: Using Next Permutation | Time Complexity: O(n * k), where n is the length of the string and k is the number of permutations to find. |
| Approach 2: Optimized Swap Calculation | Time Complexity: O(n * k), where obtaining the next permutation takes O(n) for each of the k iterations. |
| Find Next Permutation + Inversion Pairs | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Next Permutation + Swap Simulation | O(k·n + n²) | O(n) | Most common solution; easy to implement and explain in interviews |
| Optimized Greedy Swap Calculation | O(k·n + n²) | O(1) | When minimizing extra memory and implementing cleaner swap counting |
Minimum Adjacent Swaps to Reach the Kth Smallest Number | LeetCode 1850 | Coders Camp • Coders Camp • 2,966 views views
Watch 9 more video solutions →Practice Minimum Adjacent Swaps to Reach the Kth Smallest Number with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor