Last Updated: 28 Dec, 2020
Maximum number in K swaps
Hard
Asked in companies
You are given two positive integers M and K, your task is to find the maximum integer possible, by swapping at most K digits of M.
You can perform a maximum of K swap operations. If the integer becomes maximum in less than K operations, you can stop and return the output.
Note:- For simplicity, you will be provided with the integer M in the form of a ‘string’ data type for easier swap operations.
Example:-
INPUT : M = 123 , K = 1
OUTPUT: 312
In the above example, K = 1, hence only 1 swap operation is available.
Operation 1: Swap 1 with 3 so the integer becomes 312
INPUT : M = 567392 , K = 3
OUTPUT: 976532
In the above example, K = 3, hence a maximum of 3 swap operation available
Operation 1: Swap 5 with 9 so the integer becomes 967352
Operation 2: Swap 6 with 7 so the integer becomes 976352
Operation 3: Swap 3 with 5 so the integer becomes 976532
INPUT : M = 751, K = 2
OUTPUT: 751
In the above example, No swaps are required as it is already the maximum possible integer with that set of digits.
INPUT : M = 3849 , K = 0
OUTPUT: 3849
In the above example, K = 0, hence no swap operations are available.
Input Format
The first line of input contains an integer 'T' representing the number of the test case. Then the test case follows.
The first line of each test case contains a string M, denoting the input integer in the form of string.
The second line of each test case contains a single integer K, denoting the maximum number of swap operations allowed.
Output Format:
For every test case, print a single string which is the maximum integer formed after doing at most K swaps.
The output of every test case will be printed in a separate line.
Note
You don’t have to print anything, it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 100
1 <= | M | <= 20
0 <= K <= 10
Time limit: 1 second
Approaches
We can take one digit at a time and swap it with its following digits forming a new integer each time. If the new integer formed is the new maximum integer, we update it. We repeat this process K times.
- We are given a function ‘FINDMAX’ which takes a string ‘M’ and an integer ‘K’ as parameters and returns a string as output.
- Maintain a string variable ‘MAX’ to store the current maximum integer string. Now create a void helper function ‘FINDMAXHELPER’ which takes string ‘M’, integer ‘K’, and string ‘MAX’ as parameters. This is the definition of our recursive function.
- The base condition of our recursive function ‘FINDMAXHELPER’ will be when K=0, meaning when no swaps are available.
- We run a nested loop with ‘I’ as the outer loop variable and ‘J’ as the inner loop variable. Run the outer loop from 0 to length of ‘M’ - 1 and the inner loop from ‘I’+1 to the length of ‘M’ or up to the end.
- In the loop, we swap the Ith and the Jth character of ‘M’. Now, we compare ‘M’ with the ‘MAX’ string. If the ‘M’ is greater than ‘MAX’, we update the ‘MAX’ string with ‘M’.
- Recursively call the function ‘FINDMAXHELPER’ with K - 1 as the updated parameter, to recurse for another K - 1 swaps.
- Finally, we backtrack and swap the Ith and Jth characters in the original string ‘M’. We return ‘MAX’ as our final answer.
In our previous approach, we take one digit at a time and swap it with its following digits. But it is clearly visible that to form the maximum integer, only the maximum digit is swapped at the front. So instead of trying all the swappable pairs, we swap the current digit with the maximum digit in the string which is not yet swapped to the front. Finding the maximum digit before the recursive call will save us a lot of unnecessary swaps.
- We are given a function ‘FINDMAX’ which takes a string ‘M’ and an integer ‘K’ as parameters and returns a string as output.
- Maintain a string variable ‘MAX’ to store the current maximum integer string. Also maintain an integer variable ’CURR’ to store the current index and initialise it with 0. Now create a void helper function ‘FINDMAXHELPER’ which takes string ‘M’, integer ‘K’, string ‘MAX’ and integer ‘CURR’ as parameters. This is the definition of our recursive function.
- Base condition of our recursive function ‘FINDMAXHELPER’ will be when K=0, meaning when no swaps are available.
- Now we run a loop from’ CURR’ to the end of the string ‘M’ and find the maximum digit in the string and store it in a variable ‘STRMAX’ .
- If ‘STRMAX’ is not equal to the current digit, we decrement the value of ‘K’ by 1.
- Now we run a loop for ‘CURR’ to end of the string ‘M’ with the loop variable ‘I’. If the Ith digit is equal to the ‘STRMAX’, we swap the ‘CURR’ digit with ‘STRMAX’
- Now, we compare ‘M’ with the ‘MAX’ string. If the ‘M’ is greater than ‘MAX’, we update the ‘MAX’ string with ‘M’.
- Recursively call the function ‘FINDMAXHELPER’ with ‘CURR’ + 1 as the updated parameter.
- Finally, we backtrack and swap the CURRth and Jth characters in the original string ‘M’. We return the string ‘MAX’ as our final answer.