Problem Description

You are given a string num representing a large integer, and an integer k. Your task is to make the integer as small as possible by performing at most k adjacent swaps on the digits of num. In each move, you can swap any two adjacent digits (i.e., swap positions i and i+1).

• You may perform up to k swaps in total, but not more.
• Each swap must be between adjacent digits only.
• Return the smallest possible integer (as a string) you can obtain by performing at most k swaps.
• There is always at least one valid solution.

Thought Process

At first glance, the problem seems to invite a brute-force approach: try all possible swaps and pick the smallest result. However, since the number can be very large and k can also be large, this would be computationally infeasible.

We need to minimize the number by moving the smallest digits as far left as possible, but we are limited by the number of adjacent swaps (k). The key insight is to always try to bring the smallest digit within the next k positions to the current position, using as few swaps as possible.

Instead of swapping blindly, we should look ahead up to k positions and select the smallest digit we can afford to move to the front. Then, we repeat this process for the next position, updating k as we use swaps.

Solution Approach

We can solve this problem using a greedy approach, iterating through each position in the string and always selecting the smallest digit within reach (i.e., within the next k positions). Here's how:

1. For each position i in num:
   • Look at the window of digits from position i to i + k (or end of string).
   • Find the smallest digit in this window.
   • Calculate how many swaps are needed to bring this digit to position i (equal to the distance between its position and i).
   • If the number of swaps needed is less than or equal to k, perform the swaps (i.e., move the digit to position i, shifting the others right), and decrease k accordingly.
   • If not, leave the digit in place and continue.
2. Continue this process for each position until you run out of swaps or reach the end of the string.
3. The resulting string is the smallest possible integer you can form using at most k adjacent swaps.

This approach is efficient because at each step, we make the locally optimal choice that leads to a globally optimal (smallest) number, given the swap constraints.

Example Walkthrough

Let's consider num = "4321" and k = 4.

1. At position 0, look at digits "4", "3", "2", "1" (positions 0 to 3, since k=4 is enough to reach all).
   • The smallest digit is "1" at position 3.
   • To bring "1" to position 0, we need 3 swaps.
   • Since 3 ≤ 4, we perform the swaps. k = 4 - 3 = 1.
   • Resulting string: "1 4 3 2"
2. At position 1, look at digits "4", "3", "2" (positions 1 to 3, k=1).
   • The smallest digit we can reach is "4" at position 1 or "3" at position 2 (needs 1 swap).
   • We can bring "3" to position 1 by swapping with "4".
   • Resulting string: "1 3 4 2", k = 0.
3. No swaps left. The result is "1 3 4 2".

Thus, the smallest possible integer is "1342".

Time and Space Complexity

Brute-force approach:

• Would try all possible sequences of up to k swaps, leading to exponential time complexity: O(n!/(n-k)!)
• Space complexity would also be high due to recursion and storing all permutations.

• For each position, we look ahead up to k positions to find the minimum digit. In the worst case, this is O(n*k).
• Space complexity is O(n) for storing the digits in a list (since strings are immutable in some languages).

In practice, this is fast enough for typical constraints in coding interviews and Leetcode.

Summary

The key to this problem is recognizing that, with limited adjacent swaps, you should always bring the smallest possible digit within reach as far left as you can, using up swaps judiciously. The greedy approach ensures optimality by always making the best local choice, and the implementation is straightforward once you understand the pattern. This strategy avoids the explosion of possibilities in brute-force methods and provides an elegant, efficient solution.

Code Implementation

class Solution:
    def minInteger(self, num: str, k: int) -> str:
        num = list(num)
        n = len(num)
        i = 0
        while k > 0 and i < n:
            # Find the smallest digit in the window [i, min(i+k, n-1)]
            pos = i
            for j in range(i+1, min(i+k+1, n)):
                if num[j] < num[pos]:
                    pos = j
            # Number of swaps needed
            swaps = pos - i
            if swaps > k:
                break
            # Bring the smallest digit to position i
            for j in range(pos, i, -1):
                num[j], num[j-1] = num[j-1], num[j]
            k -= swaps
            i += 1
        return ''.join(num)
      

class Solution {
public:
    string minInteger(string num, int k) {
        int n = num.size();
        int i = 0;
        while (k > 0 && i < n) {
            int pos = i;
            for (int j = i + 1; j < n && j - i <= k; ++j) {
                if (num[j] < num[pos]) {
                    pos = j;
                }
            }
            int swaps = pos - i;
            if (swaps > k) break;
            for (int j = pos; j > i; --j) {
                swap(num[j], num[j - 1]);
            }
            k -= swaps;
            ++i;
        }
        return num;
    }
};
      

class Solution {
    public String minInteger(String num, int k) {
        char[] arr = num.toCharArray();
        int n = arr.length;
        int i = 0;
        while (k > 0 && i < n) {
            int pos = i;
            for (int j = i + 1; j < n && j - i <= k; j++) {
                if (arr[j] < arr[pos]) {
                    pos = j;
                }
            }
            int swaps = pos - i;
            if (swaps > k) break;
            for (int j = pos; j > i; j--) {
                char temp = arr[j];
                arr[j] = arr[j - 1];
                arr[j - 1] = temp;
            }
            k -= swaps;
            i++;
        }
        return new String(arr);
    }
}
      

var minInteger = function(num, k) {
    let arr = num.split('');
    let n = arr.length;
    let i = 0;
    while (k > 0 && i < n) {
        let pos = i;
        for (let j = i + 1; j < n && j - i <= k; j++) {
            if (arr[j] < arr[pos]) {
                pos = j;
            }
        }
        let swaps = pos - i;
        if (swaps > k) break;
        for (let j = pos; j > i; j--) {
            [arr[j], arr[j - 1]] = [arr[j - 1], arr[j]];
        }
        k -= swaps;
        i++;
    }
    return arr.join('');
};