Find Maximum number possible by doing at-most K swaps

The problem, simply

You get a number as a string of digits, and a number k. One swap means picking two digits and trading their places. You may do at most k swaps.

Give back the biggest number you can make.

A story to remember it

Picture it

Examples

Way 1: the simple way

Try every pair of spots as the next swap, but only when it makes the left digit bigger. Go k levels deep, and remember the biggest number seen anywhere.

1. Compare the current number with the best and keep the bigger one.
2. If no swaps are left, stop.
3. For every pair i < j with num[i] < num[j]: swap, go one level deeper with k - 1, then swap back.

class Solution {
    private String best;

    public String findMaximumNum(String num, int k) {
        best = num;
        tryAll(num.toCharArray(), k);
        return best;
    }

    private void tryAll(char[] num, int k) {
        String now = new String(num);
        if (now.compareTo(best) > 0) best = now;   // same length, so text order is number order
        if (k == 0) return;
        for (int i = 0; i < num.length - 1; i++) {
            for (int j = i + 1; j < num.length; j++) {
                if (num[i] < num[j]) {              // only swaps that grow the left spot
                    swap(num, i, j);
                    tryAll(num, k - 1);
                    swap(num, i, j);                // undo
                }
            }
        }
    }

    private void swap(char[] a, int i, int j) {
        char t = a[i]; a[i] = a[j]; a[j] = t;
    }
}

How long it takes: each level tries up to n * n / 2 pairs and we go k levels deep, and each number is copied in O(n). That is O(n^(2k) * n). Extra room: the call stack is k deep and we hold a copy of the number, O(n).

Way 2: the clever way

A smart swap always puts the biggest possible digit as far left as possible. So walk the spots from left to right.

1. At spot idx, find the biggest digit to its right.
2. If the digit at idx is already that big, move to idx + 1. This costs no swap.
3. Otherwise, the biggest digit may appear more than once. Try swapping with each copy. For each one: swap, update the best, go to idx + 1 with k - 1, swap back.
4. Stop when no swaps are left or the spots run out.

Why try every copy? The copy you pick decides which small digit gets sent where, and that changes what later swaps can fix.

class Solution {
    private String best;

    public String findMaximumNum(String num, int k) {
        best = num;
        solve(num.toCharArray(), k, 0);
        return best;
    }

    private void solve(char[] num, int k, int idx) {
        if (k == 0 || idx == num.length) return;

        char max = num[idx];                         // biggest digit from idx to the end
        for (int i = idx + 1; i < num.length; i++) {
            if (num[i] > max) max = num[i];
        }

        if (max == num[idx]) {                       // already the biggest, move on for free
            solve(num, k, idx + 1);
            return;
        }

        for (int i = idx + 1; i < num.length; i++) {
            if (num[i] == max) {                     // try every copy of the biggest digit
                swap(num, idx, i);
                String now = new String(num);
                if (now.compareTo(best) > 0) best = now;
                solve(num, k - 1, idx + 1);
                swap(num, idx, i);                   // undo
            }
        }
    }

    private void swap(char[] a, int i, int j) {
        char t = a[i]; a[i] = a[j]; a[j] = t;
    }
}

How long it takes: each swap level branches into at most n copies, there are at most k swap levels, and each step scans and copies the number in O(n). That is O(n^k * n), and usually far less, because most digits have only one copy. Extra room: O(n) for the call stack and the copy.

Watch out for

• Spending a swap when the digit is already the biggest. Move on for free, or you waste swaps.
• Comparing numbers with Integer.parseInt. The number may be too long. Since all strings have the same length, compareTo gives the right order.
• Updating the best only at the end of a branch. Update it after every swap, because fewer than k swaps may already give the best.

What interviewers ask next

• Only one swap allowed (LeetCode 670). Then the rightmost copy is right: for each digit, remember the last spot where it appears, and find the first spot that has a bigger digit later. That is O(n).
• Exactly k swaps, not at most. Leftover swaps can be wasted in pairs: swap two digits, then swap them back. One single leftover swap can be wasted on two equal digits, if the number has any. If not, run the full search of Way 1 and accept a number only when exactly k swaps were used.
• Smallest number instead of biggest. Same idea with the smallest digit, but the first spot cannot get a 0, because that would remove a digit.
• Only swaps of neighbors allowed. Then greedily bring the biggest digit within the next k + 1 spots to the front, paying its distance in swaps.

Remember this

Grown-up words: the spots are indices, trying each copy and undoing it is backtracking, keeping the biggest seen is a global best, and skipping useless swaps is pruning.