Minimum Possible Integer After At Most K Adjacent Swaps On Digits - Leetcode Solution

Problem Statement:

The problem states that there is an integer represented as a string. We need to minimize the integer by performing at most K adjacent swaps on the digits. Each swap will shift the digit to the adjacent position. For example, if we swap the i-th and (i+1)-th digit then the i-th digit will move to position (i+1) and (i+1)-th digit will move to position i. We need to return the minimum possible integer after performing the at most K swaps.

Solution:

One way to solve the problem is to use the concept of selection sort. In selection sort, we select the smallest element from the remaining elements and put it at the beginning of the array. We repeat this process until all the elements are sorted. We can use a similar approach here. We will start from the beginning of the integer string and find the smallest digit from the remaining digits within the range of K adjacent swaps. We will swap this digit with the current digit and reduce the value of K accordingly. If we are not able to find a smaller digit within the range of K adjacent swaps, we move to the next digit.

Let's take an example to illustrate this approach. Let's say the input integer is "34521" and K=1. We need to minimize the integer by performing at most 1 adjacent swap. The first digit is 3. We can swap this digit with the smallest digit within the range of K adjacent swaps. The available range of adjacent swaps is [0,1]. The smallest digit in this range is 2. We can swap 3 with 2 and reduce the value of K by 1. The integer becomes "24531" and K=0. Now, we move to the next digit which is 4. The available range of adjacent swaps is [0,1]. The smallest digit in this range is 3. We can swap 4 with 3 and reduce the value of K by 1. The integer becomes "23541" and K=0. Now, we move to the next digit which is 5. The available range of adjacent swaps is [0,0]. We cannot perform any swap on this digit as K=0. Similarly, we move to the next digit which is 2. The available range of adjacent swaps is [0,1]. The smallest digit in this range is 1. We can swap 2 with 1 and reduce the value of K by 1. The integer becomes "13542" and K=0. Finally, we move to the last digit which is 1. There is no available range of adjacent swaps for this digit as it is the last digit of the integer.

Therefore, the minimum possible integer after at most K adjacent swaps on digits is "13542".

The time complexity of the above algorithm is O(n^2) as we need to iterate over all the digits and for each digit, we need to find the smallest digit within the range of adjacent swaps. The space complexity is O(n) as we need to store the integer as a string.

1