Maximum swap: largest number from one digit swap

Given a non-negative integer, you may swap two of its digits at most once. Return the largest number you can make.

Interface

Unless you agree on a different interface with the interviewer, assume:

• maximum_swap(num: int) -> int

Example

maximum_swap(2736)   ->  7236    # swap 2 and 7
maximum_swap(9973)   ->  9973    # already the largest
maximum_swap(1993)   ->  9913    # swap the 1 with the last 9
maximum_swap(98368)  ->  98863
maximum_swap(120)    ->  210

Constraints

• 0 <= num <= 10^9.
• Target O(L) time for L digits.

Clarifying questions

• Is the input an integer or a string, and can it have leading zeros?
• Is "at most once" allowing no swap at all?
• With equal digits available, which one should be swapped?

What a strong answer covers

• Record the last index of each digit 0 to 9.
• Scan from the most significant digit; for each, look from 9 down to one more than the current digit for a digit whose last index lies to the right. Swap with that last occurrence and stop.
• Why the rightmost copy of the larger digit is the right choice (1993 must become 9913, not 9193).
• O(L) time because the inner loop is at most 10 steps; O(L) space for the digits.
• Tests: one digit, all equal digits, already descending, a zero in the number.

Follow-ups

• Return the smallest number with one swap, without creating a leading zero.
• Allow up to k swaps.
• The number has a million digits and arrives as a string.