All problems

Maximum Swap

Medium · greedy

You are given a non-negative whole number written out as a string of digits, num. You may swap any two of its digits at most once, or not swap at all.

Return the largest number you can end up with, as a string of digits of the same length.

The input has no leading zeros, except that the number zero is written "0".

Examples

Example 1

Input: num = "2736"

Output: "7236"

Swap the 2 and the 7. No other single swap gives a bigger number.

Example 2

Input: num = "9973"

Output: "9973"

The digits already go from largest to smallest, so no swap helps.

Example 3

Input: num = "1993"

Output: "9913"

Swap the 1 with the second 9. Using the first 9 would give 9193, which is smaller.

Constraints

• 1 <= len(num) <= 100
• num contains only the digits 0 to 9
• num has no leading zeros unless it is exactly "0"