How to perform K-swap operations on an N-digit integer to get maximum possible number

Question

I recently went through an interview and was asked this question. Let me explain the question properly:

Given a number M (N-digit integer) and K number of swap operations(a swap operation can swap 2 digits), devise an algorithm to get the maximum possible integer?
Examples:
M = 132 K = 1 output = 312
M = 132 K = 2 output = 321
M = 7899 k = 2 output = 9987

My solution ( algorithm in pseudo-code). I used a max-heap to get the maximum digit out of N-digits in each of the K-operations and then suitably swapping it.

for(int i = 0; i<K; i++) {     int max_digit_currently = GetMaxFromHeap();     // The above function GetMaxFromHeap() pops out the maximum currently and deletes it from heap      int index_to_swap_with = GetRightMostOccurenceOfTheDigitObtainedAbove();     // This returns me the index of the digit obtained in the previous function       // .e.g If I have 436659 and K=2 given,        // then after K=1 I'll have 936654 and after K=2, I should have 966354 and not 963654.      // Now, the swap part comes. Here the gotcha is, say with the same above example, I have K=3.     // If I do GetMaxFromHeap() I'll get 6 when K=3, but I should not swap it,      // rather I should continue for next iteration and      // get GetMaxFromHeap() to give me 5 and then get 966534 from 966354.      if (Value_at_index_to_swap == max_digit_currently)         continue;     else         DoSwap(); } 

Time complexity: O(K*( N + log_2(N) ))
// K-times [log_2(N) for popping out number from heap & N to get the rightmost index to swap with]

The above strategy fails in this example:
M = 8799 and K = 2
Following my strategy, I'll get M = 9798 after K=1 and M = 9978 after K=2. However, the maximum I can get is M = 9987 after K=2.

What did I miss?
Also suggest other ways to solve the problem & ways to optimize my solution.

Answer 1

I think the missing part is that, after you've performed the K swaps as in the algorithm described by the OP, you're left with some numbers that you can swap between themselves. For example, for the number 87949, after the initial algorithm we would get 99748. However, after that we can swap 7 and 8 "for free", i.e. not consuming any of the K swaps. This would mean "I'd rather not swap the 7 with the second 9 but with the first".

So, to get the max number, one would perform the algorithm described by the OP and remember the numbers which were moved to the right, and the positions to which they were moved. Then, sort these numbers in decreasing order and put them in the positions from left to right.

This is something like a separation of the algorithm in two phases - in the first one, you choose which numbers should go in the front to maximize the first K positions. Then you determine the order in which you would have swapped them with the numbers whose positions they took, so that the rest of the number is maximized as well.

Not all the details are clear, and I'm not 100% sure it handles all cases correctly, so if anyone can break it - go ahead.