LeetCode 1505: Minimum Possible Integer After at Most K Adjacent Swaps On Digits

Explanation:

To solve this problem, we can use a greedy approach. We iterate over each digit of the input number from left to right. For each digit, we check the range of possible positions where it can be moved based on the remaining swaps available. We choose the smallest digit that can be moved to the current position and update the remaining swaps accordingly.

Algorithm:

1. Initialize an array pos to keep track of the positions of each digit in the input number.
2. Iterate over each digit of the input number from left to right.
3. For the current digit, determine the range of positions it can be moved to based on the remaining swaps available.
4. Choose the smallest digit that can be moved to the current position within the range and update the remaining swaps accordingly.
5. Update the pos array to reflect the new position of the digit.
6. Construct the minimum possible integer using the updated positions in the pos array.

Time Complexity:

The time complexity of this approach is O(n^2) where n is the length of the input number.

Space Complexity:

The space complexity is O(n) where n is the length of the input number. :

class Solution {
    public String minInteger(String num, int k) {
        char[] arr = num.toCharArray();
        int n = arr.length;
        int[] pos = new int[10];
        
        for (int i = 0; i < n; i++) {
            if (k == 0) break;
            for (int j = 0; j < 10; j++) {
                if (pos[j] == 0) continue;
                int steps = pos[j] - i;
                if (steps <= k) {
                    k -= steps;
                    for (int l = j; l > arr[i] - '0'; l--) {
                        pos[l]--;
                    }
                    pos[arr[i] - '0']++;
                    arr[pos[j]] = arr[i];
                    break;
                }
            }
            pos[arr[i] - '0'] = i;
        }
        
        return new String(arr);
    }
}