Maximum number in K swaps

Hard
0/120
Average time to solve is 15m
8 upvotes
Asked in companies
AmdocsRoyal Bank of Scotland

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
4
142375 
1
567392 
3
7861 
0
9876 
5
Sample Output 1:
742315
976532
7861
9876
Explanation of Sample Input 1:
In the first test case, K = 1, hence only 1 swap is allowed
Operation 1: Swap 1 with 7 so the integer becomes 742315
Hence, the output is 742315

In the second test case, K = 3, hence a maximum of 3 swaps are allowed
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
Hence, the output is 976532

In the third test case, K = 0, hence no swap operations are available
Hence, the output is 7861

In the fourth test case, no swaps are required as it is already the maximum possible integer with that set of digits.
Sample Input 2:
3
7293 
2
589 
1
25610 
2
Sample Output 2:
9732
985
65210
Hint

Can you think of a recursive algorithm? 

Approaches (2)
Basic Approach

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.

 

  1. We are given a function ‘FINDMAX’ which takes a string ‘M’ and an integer ‘K’ as parameters and returns a string as output.
  2. 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.
  3. The base condition of our recursive function ‘FINDMAXHELPER’ will be when K=0, meaning when no swaps are available.
  4. 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.
  5. 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’.
  6. Recursively call the function ‘FINDMAXHELPER’ with K - 1 as the updated parameter, to recurse for another K - 1 swaps.
  7. Finally, we backtrack and swap the Ith and Jth characters in the original string  ‘M’. We return ‘MAX’ as our final answer.
Time Complexity

O((N^2)^K), where N is the size of the input string and K is the number of swaps allowed

 

As clearly seen, after every recursive call, N^2 recursive calls are generated for a total of K swaps. Hence, the worst-case time complexity is O((N^2)^K).

Space Complexity

O(N), where N is the size of the input string.

 

The string variable ‘MAX’ stores the string ‘M’ which is of size N. Hence the space complexity is O(N).

Code Solution
(100% EXP penalty)
Maximum number in K swaps
Full screen
Console