Welcome back, dear reader. So, how is it going? We are back with yet another interesting problem in recursion and backtracking. This problem is called

**Important Links :** Maximum Number After K Swaps.

Maximum Number After K Swaps

Optimism is an occupational hazard of programming: feedback is the treatment.

~ Kent Beck

Maximum Number After K Swaps

Welcome back, dear reader. So, how is it going? We are back with yet another interesting problem in recursion and backtracking. This problem is called

**Important Links :** Maximum Number After K Swaps.

Understanding problem:

We are given a string which represents an integer number and we are given an integer K. We have to give the maximum number that we can generate by performing at most K swaps in the number. For instance, consider the input shown below:

As you can see above, we generated the maximum possible number from only 3 swaps and we were allowed maximum (at most) 4 swaps. We recommend you refer to the Maximum Number with At Most K Swaps video to understand the question completely and clear your doubts regarding it if any.

Approach :

The problem can be solved by applying the simple levels and options method. Here, on each level, we will keep one swap i.e. each level will represent a swap. So, the maximum height of the recursion tree will be K where K is the maximum number of swaps that we are allowed. So, let us start by placing the number at the 0th level and continue with the levels and options method.

The Levels and Options Method:

Let us consider the input string given to us is "38164" and the maximum number of swaps allowed to us are 2.

See, we have talked about what the levels are going to represent. So, at each level, we will perform one swap. But, there is something called a valid swap that we need to consider. What do we mean by this? We cannot swap any two random characters in the string. For instance, if the input string given to us is "7654321", then we cannot make any larger number even if we are provided with an infinite number of swaps as it is the maximum possible number.**So, the concept is that if we want to swap two characters then the lower indexed character or the character at the left should be smaller than the character at the right.**

Let us now start with the procedure.

So, the input string is "38164". We will keep a variable 'i' on the 0th index of the string initially and the variable 'j' will start from i+1. We will swap the jth character with the ith character only if the ith character is smaller than the jth+ character. For instance, we find that the character at the 1st index is smaller than the character at the 0th index. So, we swapped them.

Since the first level represents only one swap, we have various other options available at this level in which we can generate a larger number with one swap. Those are all shown in the image above (img-2).

Note that the string "38614" and "38461" are generated when the variable 'i' is kept on index 2 and the variable 'j' on index 3 and 4 respectively.

Also, note that we have not swapped '3' with '1' because of the reason already discussed above. The next level will show all the possible numbers that can be generated by performing 2 swaps. So, try to draw the tree for the next level.

As you can see above, we have generated a lot of strings by swapping two more characters only. So, we iterate through every string from i=0 to i=length of the string-1, to check whether a swap is possible or not and if it is, we swap those characters and generate new strings.

Since we were given at most 2 swaps only, we have to stop the procedure here. The maximum value when all the strings obtained are converted to integer will be our answer. In this case, it is 86134. We know that this is not the maximum number that can be generated using the given characters but it is the maximum number that can be generated when we are given at most 2 swaps. Can you think of the reason?

Using Selection Sort (Type of Algorithm):

See, we are given the input string "38164". To generate the largest number from 2 swaps, our aim should be to bring the largest character at 0th index and the second largest character at 1st index. So, let's do the same.

So, an efficient way to solve this problem without recursion and backtracking can be to perform K iterations and select the larger characters to come forward. This is like selection sort but instead of bringing the smallest character at the front, we are bringing the largest, isn't it? Think!!!

Dear reader, we recommend you refer to the solution video to understand the recursion and backtracking approach completely.

import java.util.*;
public class Main {
static String max;
public static String swap(String str, int i ,int j)
{
char ith = str.charAt(i);
char jth = str.charAt(j);
String left = str.substring(0,i);
String middle = str.substring(i+1,j);
String right = str.substring(j+1);
return left + jth + middle + ith + right;
}
public static void findMaximum(String str, int k) {
//write your code here
if(Integer.parseInt(str) > Integer.parseInt(max))
{
max= str;
}
if(k==0)
{
return;
}
for(int i=0;i< str.length()-1;i++)
{
for(int j = i+1;j< str.length();j++)
{
str = swap(str,i,j);
findMaximum(str,k-1);
str = swap(str,i,j);
}
}
}
public static void main(String[] args) {
Scanner scn = new Scanner(System.in);
String str = scn.next();
int k = scn.nextInt();
max = str;
findMaximum(str, k);
scn.close();
System.out.println(max);
}
}

java; true";

We recommend you refer to the solution video () to understand the above code completely and clear your doubts regarding it if any. We also suggest you try to solve this problem with the selection sort type procedure discussed above yourself and see if you are able to come up with the solution. Now that we have completed the discussion, let us move to the time and space complexity analysis.

Analysis:

Time Complexity

Space Complexity

Space Complexity

So, dear reader, we hope that you have understood the above analysis as well. If you still have any doubts, we recommend you refer to the complete solution video to clear them. With this, we have completed our discussion on this problem.

**Important Links :** complete solution video

Suggestions:

Here are some suggestions from our side that you do not want to miss:

- We highly recommend you refer to the complete solution video once even if you have solved the problem as it gives an immense insight into the problem and you may learn a few things here and there.
- We also suggest that you try to solve this problem with an efficient method. A hint of the method is provided in the article above only. Try to implement it on your own. Also, it might not be the only method. So, think hard and work hard. Till then, Happy Coding!!