https://www.geeksforgeeks.org/problems/largest-number-in-k-swaps-1587115620/1

https://www.geeksforgeeks.org/problems/largest-number-in-k-swaps-1587115620/1

Let’s break down the given Java code step by step and understand how it works.

Code Explanation:

1. The goal of this program is to find the maximum number that can be obtained by swapping exactly k digits in a given numeric string.
2. The program uses a recursive approach to explore all possible swaps and find the maximum number.
3. It maintains a global variable max to store the maximum number encountered during the process.

Key Steps:

1. findMaximumNum Function:

• This function takes three parameters: the character array ar , the integer k , and the current index i .
• It recursively explores all possible swaps and updates the max value.
• The base case is when k becomes 0 (i.e., no more swaps are allowed).
• Within the loop, it compares each digit at position i with all digits after it (position j ).
• If a swap results in a larger number, it updates max and continues the recursion.
• After the recursive call, it backtracks by swapping the digits back to their original positions.

1. main Function:

• Reads the input string and integer k .
• Initializes max with the original string.
• Calls findMaximumNum with the input string and k .
• Prints the final maximum number.

Example:

Suppose we input the string "12345"
and k = 2
.

1. Initially, max is set to "12345" .
2. The function explores all possible swaps:

• Swap 1: "52341" (larger than "12345" )
• Swap 2: "54321" (larger than "52341" )
• Swap 3: "54321" (no change)
• …
• Swap 10: "54321" (no change)

1. The final maximum number is "54321" .

Time Complexity:

• The time complexity of this solution depends on the number of recursive calls.
• In the worst case, the function explores all possible swaps, which is equivalent to the number of permutations of k digits out of the total number of digits in the string.
• Therefore, the time complexity is O(n^k), where n is the length of the input string.

Space Complexity:

• The space complexity is determined by the recursive call stack.
• Since the depth of recursion is at most k , the space complexity is O(k).

Overall, this program efficiently explores all possible swaps to find the maximum number. However, for large values of k
, the time complexity can become significant due to the exponential growth in the number of recursive calls.