Smallest Integer After K Adjacent Swaps

Hard
0/120
Average time to solve is 25m
profile
Contributed by
4 upvotes
Asked in company
Adobe

Problem statement

You are given a string ‘NUM’ of length ‘N’, representing the digits of a very large number and an integer ‘K’. You can swap any two adjacent digits of ‘NUM’ at most ‘K’ times.

Your task is to find the minimum integer that can be obtained and return it as a string.

Example : 
‘NUM’ = “5432”, ‘N’ = 4 and ‘K’ = 4.

We can perform the following ‘4’ swaps to obtain the minimum integer from “5432”:

example

Thus, you should return the string “2453” as the answer.
Note : 
1. ‘NUM’ doesn’t have leading zeroes.
2. The resultant minimum integer can have leading zeroes.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line of input contains an integer ‘T’ which denotes the number of test cases. Then, the ‘T’ test cases follow.

The first line of each test case contains two integers, ‘N’ and ‘K’, denoting the number of digits in ‘NUM’ and the maximum allowed swaps.

The second line of each test case contains the string ‘NUM’.
Output Format : 
For every test case, return the string representing the minimum integer obtained by performing at most ‘K’ swaps.
Note : 
You do not need to print anything; it has already been taken care of. Just implement the function.
Constraints : 
1 <= T <= 10
1 <= N <= 500
1 <= k <= 10^4

The string ‘NUM’ contains only digits in the range [0, 9].

Time limit: 1 sec

Sample Input 1 :

2
5 3
90761
4 5
1324

Sample Output 1 :

06971
1234

Explanation Of Sample Input 1 :

Test Case 1:
We can perform the following ‘3’ swaps to obtain the minimum integer from “90761”:

sample1

Thus, you should return the string “06971” as the answer.

Test Case 2:
We can perform the following swap to obtain the minimum integer from “1324”:

sample2

Thus, you should return the string “1234” as the answer.

Sample Input 2 :

2
6 12
654321
5 100
14689

Sample Output 2 :

123654
14689
Hint

Think in a greedily manner i.e. the most significant (leftmost) digit should be the minimum of the first ‘K + 1’ digits (given that ‘K + 1 <= N’)

Approaches (3)
Greedy Approach

The idea behind the greedy approach:

  • The most significant (leftmost) digit should be the minimum of the first ‘K + 1’ digits (given that ‘K + 1 <= N’).
  • If there are multiple such values, then we must swap the leftmost digit (let’s say at index ‘ID’), as it would consume less number of swaps.
  • After that, swap the digits from ‘ID’ to the leftmost digit one by one, such that the digit at ‘ID’ becomes the leftmost digit.
    • Update the value of ‘K’ accordingly and perform the same steps for each digit until we reach the last digit or ‘K’ is exhausted.

 

We need two levels of loops, the outer loop to traverse the integer ‘NUM’, and the inner (nested) loop to find the smallest leftmost digit among the next ‘K’ digits and swap the digits in between.

 

Algorithm:

  • Run a loop where ‘i’ ranges from ‘0’ to ‘N - 1’:
    • Set ‘index = i’.
    • Run a loop where ‘j’ ranges from ‘i + 1’ to ‘K - 1’:
      • If ‘K < j - i’, then the digit at ‘j’ needs more than ‘K’ swaps to move to position ‘i’:
        • Break the loop.
      • If ‘NUM[index] > NUM[j]’, then update ‘index’ as the digit at ‘j’ is smaller than the digit at ‘index’:
        • ‘index = j’.
    • Run a loop where ‘j’ ranges from ‘index’ to ‘i’, to swap the digits between ‘index’ to ‘i’:
      • ‘swap(NUM[j], NUM[j - i])’.
    • ‘K -= (index - i)’. The number of swaps to move ‘NUM[index]’ to position ‘i’.
  • Return ‘NUM’ as the answer.
Time Complexity

O(N^2), where ‘N’ is the number of digits in ‘NUM’.

 

We use two nested loops that perform ‘N*(N-1)/2’ operations in the worst-case scenario. Thus, the time complexity is ‘O(N^2)’.

Space Complexity

O(1),

 

Since we are not using any extra space, space complexity is constant.

Code Solution
(100% EXP penalty)
Smallest Integer After K Adjacent Swaps
Full screen
Console