Problem

You are given a string num representing the digits of a very large integer and an integer k. You are allowed to swap any two adjacent digits of the integer at most k times.

Return the minimum integer you can obtain also as a string.

Examples

Example 1:

graph LR;
	A("4321") --- B("3421") --- C("3412") --- D("3142") --- E("1342")
  
1
2
3
4
5

Input:
num = "4321", k = 4
Output:
 "1342"
Explanation: The steps to obtain the minimum integer from 4321 with 4 adjacent swaps are shown.

Example 2:

1
2
3
4
5

Input:
num = "100", k = 1
Output:
 "010"
Explanation: It's ok for the output to have leading zeros, but the input is guaranteed not to have any leading zeros.

Example 3:

1
2
3
4
5

Input:
num = "36789", k = 1000
Output:
 "36789"
Explanation: We can keep the number without any swaps.

Solution

Method 1 - Greedy

Here are the key insights:

  • The problem revolves around creating the smallest lexicographical sequence possible within adjacent swaps.
  • Prioritise moving smaller digits closer to the front while respecting the k allowed swaps.
  • This can be achieved using a greedy approach:
    • Iterate through the digits of num and repeatedly bring the smallest digit within the k-range of the current position to the front.

Algorithms

  • Convert num into a list for mutable operations.
  • Traverse the string and at every step:
    • Look at the next k digits.
    • Bring the smallest digit in this range to the current position using minimal swaps.
    • Deduct the number of swaps used from k.
    • If k becomes 0, stop as no further swaps can be made.
  • Join the modified list and return it as a string.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

class Solution {

    public String minInteger(String num, int k) {
        char[] arr = num.toCharArray();
        int n = arr.length;

        for (int i = 0; i < n && k > 0; i++) {
            int pos = i;

            // Find the smallest digit within k-range
            for (int j = i + 1; j < n && j - i <= k; j++) {
                if (arr[j] < arr[pos]) {
                    pos = j;
                }
            }

            // Bring smallest digit found to position i
            for (int j = pos; j > i; j--) {
                char temp = arr[j];
                arr[j] = arr[j - 1];
                arr[j - 1] = temp;
            }

            // Update remaining swaps
            k -= (pos - i);
        }

        return new String(arr);
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution:
    def minInteger(self, num: str, k: int) -> str:
        n = len(num)
        arr = list(num)  # Convert to list for mutable operations
        
        for i in range(n):
            if k == 0:
                break
            
            # Find the smallest digit within the k range
            pos = i
            for j in range(i + 1, min(n, i + k + 1)):
                if arr[j] < arr[pos]:
                    pos = j
            
            # Bring smallest digit to position i
            for j in range(pos, i, -1):
                arr[j], arr[j - 1] = arr[j - 1], arr[j]
            
            # Update remaining swaps
            k -= (pos - i)
        
        return ''.join(arr)

Complexity

  • ⏰ Time complexity: O(n*k). Evaluating the smallest digit in a k-length window takes O(k) for each digit, resulting in O(n*k) where n is the length of the string.
  • 🧺 Space complexity: O(n) due to the mutable list representation of num.