Most Quantity by swapping digits between positions with identical parity

Given a optimistic integer N, the duty is to search out the most important potential worth of N after any variety of swaps is made between digits which are current in positions with the identical parity.

Examples:

Enter: N = 12345
Output: 54321
Rationalization: Swap 1 with 5 [both in odd positions],  
and a couple of with 4 [both in even positions] to acquire 54321.

Enter: N = 738946
Output: 897643

Method: 

The issue may be solved by storing odd listed and even listed digits in two maxHeaps, and creating new quantity that has each parity listed digits sorted in decending order.

The next steps can be utilized to resolve this downside:

• Initialize 2 maxHeaps even and odd.
• Iterate over digits of the quantity and retailer even listed digits in even maxHeap and odd listed digits in odd maxHeap.
• Create a brand new quantity by popping values from maxHeaps, now new quantity would have each even listed digits and odd listed digits in lowering order.
• Return this quantity as it’s the most.

Beneath is the implementation of the above method.

Time Complexity: O(log N)
Auxiliary House: O(log N)