Problem Description

Given a string num representing a large integer and an integer k, you need to find the k-th smallest "wonderful" integer and calculate the minimum number of adjacent swaps needed to transform num into it.

A wonderful integer is defined as any permutation of the digits in num that is greater in value than num. These wonderful integers are ordered from smallest to largest.

For example, with num = "5489355142":

• The 1st smallest wonderful integer is "5489355214"
• The 2nd smallest wonderful integer is "5489355241"
• The 3rd smallest wonderful integer is "5489355412"
• The 4th smallest wonderful integer is "5489355421"

Your task is to:

1. Find the k-th smallest wonderful integer (which is the k-th next permutation of num in lexicographical order)
2. Calculate the minimum number of adjacent digit swaps needed to transform the original num into this k-th wonderful integer

The problem guarantees that the k-th smallest wonderful integer exists for the given inputs.

The solution involves two main steps:

• Using the next permutation algorithm k times to find the target arrangement
• Calculating the minimum swaps by counting inversion pairs between the original and target arrangements, handling duplicate digits carefully by greedily assigning indices

Intuition

To find the k-th smallest wonderful integer, we need to understand that wonderful integers are essentially the next permutations of num in lexicographical order. The k-th smallest wonderful integer is simply the result of applying the next permutation operation k times starting from num.

Once we have the target permutation, the key insight is that the minimum number of adjacent swaps needed to transform one arrangement into another equals the number of inversion pairs between them. An inversion pair occurs when an element that should come later appears before an element that should come earlier.

Consider a simpler problem first: if all digits were unique, we could map each digit to its position index. For example, if num = "543" and target is "453", we map positions: 5→0, 4→1, 3→2. Then for the target "453", we get position sequence [1, 0, 2]. The inversions in this sequence (where a larger index appears before a smaller one) tell us exactly how many adjacent swaps are needed.

However, when duplicate digits exist, we need to be careful about which occurrence of a digit maps to which position. The greedy approach works here: for each digit in the target string, we should map it to the earliest available occurrence in the original string. This minimizes the total displacement and thus the number of swaps.

By maintaining arrays that track where each digit appears in the original string and processing the target string from left to right, we can build an array of position mappings. The number of inversion pairs in this array gives us our answer - each inversion represents a pair of elements that are out of order and will eventually need to be swapped.

Learn more about Greedy and Two Pointers patterns.

Solution Approach

The solution consists of two main parts: finding the k-th next permutation and calculating the minimum swaps needed.

Part 1: Finding the k-th Next Permutation

The next_permutation function implements the standard algorithm to find the next lexicographically greater permutation:

1. Starting from the right, find the first index i where nums[i] < nums[i+1]. This is the "pivot" position where we can make the number larger.
2. If no such i exists (array is in descending order), there's no next permutation.
3. Find the rightmost element nums[j] that is greater than nums[i].
4. Swap nums[i] and nums[j].
5. Reverse the suffix starting at nums[i+1] to get the smallest possible arrangement after the pivot.

We call this function k times on a list copy of num to get the k-th wonderful integer.

Part 2: Calculating Minimum Swaps via Inversion Pairs

To handle duplicate digits, we use the following approach:

1. Build position arrays: Create a 2D array d where d[digit] contains all positions where that digit appears in the original num. For example, if num = "5355", then d[5] = [0, 2, 3] and d[3] = [1].

2. Map target to positions: For each digit in the target string s, assign it to the next available position from the original string:

   • Use an idx array to track which occurrence of each digit we've used
   • For each character c in target string s, get its digit value j
   • Assign position arr[i] = d[j][idx[j]] and increment idx[j]

   This greedy assignment ensures we use positions in order, minimizing total displacement.

3. Count inversion pairs: The final step counts how many pairs (i, j) exist where i < j but arr[i] > arr[j]:

   sum(arr[j] > arr[i] for i in range(n) for j in range(i))

   Each inversion pair represents elements that are out of order and will need to be swapped.

For example, if num = "5489355142" and we want the 1st wonderful integer "5489355214":

• The digit mapping would track that the '1' at position 7 in original moves to position 8 in target
• The '4' at position 8 moves to position 7
• The '2' at position 9 moves to position 9
• This creates one inversion pair, requiring 1 swap

The time complexity is O(k * n + n^2) where n is the length of the string - k iterations for finding the permutation and n^2 for counting inversions.

Example Walkthrough

Let's walk through a concrete example with num = "2431" and k = 2.

Step 1: Find the 2nd wonderful integer

Starting with num = "2431", we apply the next permutation algorithm twice:

First permutation:

• Find pivot: From right, find first i where nums[i] < nums[i+1]. Here, i = 1 (since 4 < 3 is false, but 2 < 4 is true)
• Find swap candidate: Find rightmost j where nums[j] > nums[i]. Here, j = 3 (1 > 2 is false, 3 > 2 is true)
• Swap positions 1 and 3: "2431" → "3421"
• Reverse suffix from position 2: "3421" → "3412" (reversing "21" gives "12")

Second permutation on "3412":

• Find pivot: i = 2 (since 1 < 2 is true)
• Find swap candidate: j = 3 (2 > 1 is true)
• Swap positions 2 and 3: "3412" → "3421"
• Reverse suffix from position 3: "3421" → "3421" (single element, no change)

So the 2nd wonderful integer is "3421".

Step 2: Calculate minimum swaps from "2431" to "3421"

Build position arrays for original num = "2431":

• d[2] = [0] (digit 2 appears at position 0)
• d[4] = [1] (digit 4 appears at position 1)
• d[3] = [2] (digit 3 appears at position 2)
• d[1] = [3] (digit 1 appears at position 3)

Map target "3421" to positions:

• Character '3' at target position 0 → use d[3][0] = 2, so arr[0] = 2
• Character '4' at target position 1 → use d[4][0] = 1, so arr[1] = 1
• Character '2' at target position 2 → use d[2][0] = 0, so arr[2] = 0
• Character '1' at target position 3 → use d[1][0] = 3, so arr[3] = 3

Result: arr = [2, 1, 0, 3]

Count inversion pairs in arr = [2, 1, 0, 3]:

• Position 0 vs 1: 2 > 1 ✓ (1 inversion)
• Position 0 vs 2: 2 > 0 ✓ (1 inversion)
• Position 0 vs 3: 2 > 3 ✗
• Position 1 vs 2: 1 > 0 ✓ (1 inversion)
• Position 1 vs 3: 1 > 3 ✗
• Position 2 vs 3: 0 > 3 ✗

Total inversions = 3

Therefore, transforming "2431" to "3421" requires 3 adjacent swaps.

We can verify this:

• "2431" → "2341" (swap positions 2,3)
• "2341" → "3241" (swap positions 0,1)
• "3241" → "3421" (swap positions 1,2)

Solution Implementation

Time and Space Complexity

Time Complexity: O(n × (k + n))

The time complexity breaks down as follows:

• The next_permutation function is called k times in the loop, and each call takes O(n) time (scanning from right to left, swapping, and reversing a portion of the array). This contributes O(k × n).
• Building the position arrays d takes O(n) time as we iterate through the original string once.
• Creating the arr array takes O(n) time as we iterate through the permuted string s once.
• The final step calculates inversions using a nested loop: sum(arr[j] > arr[i] for i in range(n) for j in range(i)), which takes O(n²) time.
• Overall: O(k × n) + O(n) + O(n) + O(n²) = O(n × k + n²) = O(n × (k + n))

Space Complexity: O(n)

The space complexity breaks down as follows:

• The list s stores a copy of the input string: O(n)
• The 2D list d stores positions of digits. Since there are at most n positions total distributed across 10 digit buckets: O(n)
• The idx array has fixed size 10: O(1)
• The arr array stores n elements: O(n)
• Overall: O(n) + O(n) + O(1) + O(n) = O(n)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Handling of Duplicate Digits

Pitfall: A naive approach might try to directly map characters from the original string to the target string without considering that duplicate digits need special handling. For example, if num = "5355" and target = "5535", simply finding where each '5' should go without tracking which '5' is which will lead to incorrect swap calculations.

Why it happens: When multiple identical digits exist, we need to decide which specific occurrence in the original maps to which occurrence in the target. An arbitrary or incorrect mapping can drastically increase the number of required swaps.

Solution: Use a greedy assignment strategy with position tracking:

• Maintain separate position lists for each digit (0-9)
• When building the permutation array, assign digits to positions in order (first occurrence to first occurrence, etc.)
• This ensures minimal total displacement and correct inversion counting

2. Modifying the Original String During Permutation Generation

Pitfall: Directly applying next_permutation on the original string or forgetting to create a copy:

# WRONG: This modifies num directly
digits = num  # This is just a reference!
for _ in range(k):
    next_permutation(digits)

# CORRECT: Create a mutable copy
target_digits = list(num)
for _ in range(k):
    next_permutation(target_digits)

Why it happens: Strings in Python are immutable, but if you accidentally work with references or forget to create a proper copy, you might lose the original configuration needed for swap calculation.

Solution: Always create a list copy of the string before applying permutation operations: target_digits = list(num)

3. Off-by-One Errors in Next Permutation Algorithm

Pitfall: Incorrectly implementing the boundary checks in the next_permutation function, particularly:

• Starting the pivot search from n-1 instead of n-2
• Using wrong comparison operators (< vs <=, > vs >=)
• Incorrect slice indices when reversing the suffix

Example of wrong implementation:

# WRONG: Starting from wrong index
pivot_index = n - 1  # Should be n - 2
while pivot_index >= 0 and digits[pivot_index] >= digits[pivot_index + 1]:
    pivot_index -= 1

Solution: Carefully implement the standard next permutation algorithm:

• Start pivot search from n-2 (second-to-last element)
• Use >= when finding the pivot (not >)
• Use <= when finding the swap element (not <)
• Reverse from pivot_index + 1 to end

4. Inefficient Inversion Counting

Pitfall: Using inefficient algorithms for counting inversions, especially for large strings. While the O(n²) approach works, for very large inputs it might be slow.

Alternative Solution (for optimization): Use merge sort or a Binary Indexed Tree (Fenwick Tree) to count inversions in O(n log n) time:

def count_inversions_optimized(arr):
    """Count inversions using merge sort approach - O(n log n)"""
    def merge_and_count(arr, temp, left, mid, right):
        i, j, k = left, mid + 1, left
        inv_count = 0
      
        while i <= mid and j <= right:
            if arr[i] <= arr[j]:
                temp[k] = arr[i]
                i += 1
            else:
                temp[k] = arr[j]
                inv_count += (mid - i + 1)
                j += 1
            k += 1
      
        while i <= mid:
            temp[k] = arr[i]
            i += 1
            k += 1
      
        while j <= right:
            temp[k] = arr[j]
            j += 1
            k += 1
      
        for i in range(left, right + 1):
            arr[i] = temp[i]
      
        return inv_count
  
    def merge_sort_and_count(arr, temp, left, right):
        inv_count = 0
        if left < right:
            mid = (left + right) // 2
            inv_count += merge_sort_and_count(arr, temp, left, mid)
            inv_count += merge_sort_and_count(arr, temp, mid + 1, right)
            inv_count += merge_and_count(arr, temp, left, mid, right)
        return inv_count
  
    n = len(arr)
    temp = [0] * n
    arr_copy = arr.copy()
    return merge_sort_and_count(arr_copy, temp, 0, n - 1)

This optimization becomes crucial when dealing with strings of length 10,000+ where the O(n²) approach might timeout.