579. One Swap Bigger
A lottery machine prints a ticket number num. Before the draw, a clerk is allowed to pick any two digit positions in the written number and swap those two digits, but may do this at most once (doing nothing is also allowed). The clerk wants the printed number to be as large as possible.
Return the largest value that can be obtained. The two chosen positions may be equal or different digits; if all digits are already arranged so that no swap can increase the value, return num unchanged. A swap that moves a 0 to the front is allowed but never helps, since the result would just be smaller.
The number has at most nine digits, so an O(d^2) check of all pairs would also pass, but the intended solution is a greedy scan using the last position of every digit, running in O(d) time and O(1) space, where d is the number of digits.
Example 1
- Input:
- num = 4815
- Output:
- 8415
- Explanation:
Swapping the 4 with the 8 gives 8415, the largest value reachable with one swap.
Example 2
- Input:
- num = 9531
- Output:
- 9531
- Explanation:
The digits are already in non-increasing order, so no swap can make the number larger.
Example 3
- Input:
- num = 1993
- Output:
- 9913
- Explanation:
Swap the leading 1 with the last 9 (not the first one) to get 9913, which beats 9193.
Constraints
0 ≤ num ≤ 100000000
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(d)
- Space
- O(1)