## Wednesday, June 29, 2016

### Find Maximum number possible by doing at-most K swaps - GeeksforGeeks

Find Maximum number possible by doing at-most K swaps - GeeksforGeeks
Given a positive integer, find maximum integer possible by doing at-most K swap operations on its digits.

Idea is to consider every digit and swap it with digits following it one at a time and see if it leads to the maximum number. We repeat the process K times. The code can be further optimized if we swap only if current digit is less than the following digit.
`void` `findMaximumNum(string str, ``int` `k, string& max)`
`{`
`    ``// return if no swaps left`
`    ``if``(k == 0)`
`        ``return``;`

`    ``int` `n = str.length();`
`    `
`    ``// consider every digit`
`    ``for` `(``int` `i = 0; i < n - 1; i++)`
`    ``{`
`     `
`        ``// and compare it with all digits after it`
`        ``for` `(``int` `j = i + 1; j < n; j++)`
`        ``{`
`            ``// if digit at position i is less than digit`
`            ``// at position j, swap it and check for maximum`
`            ``// number so far and recurse for remaining swaps`
`            ``if` `(str[i] < str[j])`
`            ``{`
`                ``// swap str[i] with str[j]`
`                ``swap(str[i], str[j]);`

`                ``// If current num is more than maximum so far`
`                ``if` `(str.compare(max) > 0)`
`                    ``max = str;`

`                ``// recurse of the other k - 1 swaps`
`                ``findMaximumNum(str, k - 1, max);`

`                ``// backtrack`
`                ``swap(str[i], str[j]);`
`            ``}`
`        ``}`
`    ``}`
`}`
1. Find minimum integer possible by doing at-least K swap operations on its digits.
2. Find maximum/minimum integer possible by doing exactly K swap operations on its digits.