Minimum Adjacent Swaps to Reach the Kth Smallest Number - Video Solutions

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.