Largest Number Possible After At Most K Swaps

  Prev   Next

Try First, Check Solution later

1. You should first read the question and watch the question video.
2. Think of a solution approach, then try and submit the question on editor tab.
3. We strongly advise you to watch the solution video for prescribed approach.

1. You are given a string which represents digits of a number.
2. You have to create the maximum number by performing at-most k swap operations on its digits.

Note -> Check out the question video and write the recursive code as it is intended without 
               changing signature. The judge can't force you but intends you to teach a concept.
Input Format 
A string S and a number K
Output Format 
A number
Question Video
Constraints 
1 <= length of S <= 30
1 <= K <= 10
Sample Input 
1234567
4
Sample Output 
7654321


  • Editorial

    Backtracking will be used to solve this question. At levels, number of swaps done till that level will be kept. At each level, at most n2 swap (Swap first character with every character to the right of it, similarly swap every second character to the right of it) can be done. All the n2 swaps will be done one by one and recursive function will be called after each swap at each level. Swap will be done only when the character to the right of the current character is more than the current character as this will only generate maximum number. When k swaps have been completed, it means no more swaps can be done, we will return. At the beginning compare the current string to the global string and if the current string is more than the global string, update the global string. Global string will be the final answer.

    Signature -

    public static void findMaximum(String str, int k)

    str - Input string

    k - Number of swaps done till that level

    Code - 

    static String max;
                                    public static void findMaximum(String str, int k) {
                                        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++) {
                                                if (str.charAt(i) < str.charAt(j)) {
                                                    str = swap(str, i, j);
                                
                                                    findMaximum(str, k - 1);
                                                    str = swap(str, i, j);
                                                }
                                            }
                                        }
                                    }
                                
                                    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;
                                    }

    java false

    Code Explained -

    max is the global string that will the store the final answer. At the beginning of the function, max is compared with the current string. If the current string is more than the max, update the max. All the n2 swaps are done at each level. Swap is only done when the character right to the current character is more than the current character. As strings are immutable in java, we generate a new string which will be equal to the swapped string.

    To generate the swapped string,

    Left = substring from starting till i.

    Middle - substring from i + 1 to j

    Right - substring from j + 1 to end

    Return (left + jth character + middle + ith character + right) (Position of jth and ith character is swapped)

    Base Case -

    When k == 0, it means all the swaps have been done, return. Print the max string in the end.

  • Asked in Companies
  • Related Topics






Video Solution

Code Solution

Run
 
Run
Id Name