Largest Number Possible After At Most K Swaps
1. You are given a string which represents digits of a number.Input Format
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.
A string S and a number KOutput Format
A numberQuestion Video
1 <= length of S <= 30Sample Input
1 <= K <= 10
1234567Sample Output
4
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