# LeetCode 670. Maximum Swap

## Description:

Given a non-negative integer, you could swap two digits at most once to get the maximum valued number. Return the maximum valued number you could get.

## Note:

• The given number is in the range $$[0, 10^8]$$

## Example:

input:

2736

output:

7236

explanation:

Swap the number 2 and the number 7.

input:

9973

output:

9973

explanation:

No swap.

## Solution:

class Solution:
def maximumSwap(self, num):
"""
:type num: int
:rtype: int
"""
numStr = repr(num)
numDigit = [int(ch) for ch in numStr]

if len(numDigit) <= 1:
return num

maxTable = [-1] * len(numDigit)

currentMax = (-1, -1)
for i in range(len(numDigit) - 1, -1, -1):
if numDigit[i] > currentMax[0]:
currentMax = (numDigit[i], i)
maxTable[i] = currentMax

for i in range(len(numDigit)):
if maxTable[i][0] > numDigit[i]:
# swap numDigit[i] and numDigit[maxTable[i][1]]
temp = numDigit[i]
numDigit[i] = numDigit[maxTable[i][1]]
numDigit[maxTable[i][1]] = temp
break

result = 0
for i in range(len(numDigit)):
result += numDigit[len(numDigit) - 1 - i] * pow(10, i)

return result


Starting backwards, keep track of a maxTable that stores the largest digit in the range [i:len(numDigit)]. Scan and compare each element in numDigit and maxTable from the right. If an element in maxTable is greater than its corresponding element in numDigit, execute the swap.