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.

Read full article from Find Maximum number possible by doing at-most K swaps - GeeksforGeeks