• Time:O(n)
• Space:O(n)

## C++

``````class Solution {
public:
int maximumSwap(int num) {
string s = to_string(num);
vector<int> lastIndex(10, -1);  // {digit: last index}

for (int i = 0; i < s.length(); ++i)
lastIndex[s[i] - '0'] = i;

for (int i = 0; i < s.length(); ++i)
for (int d = 9; d > s[i] - '0'; --d)
if (lastIndex[d] > i) {
swap(s[i], s[lastIndex[d]]);
return stoi(s);
}

return num;
}
};
``````

## JAVA

``````class Solution {
public int maximumSwap(int num) {
char[] s = Integer.toString(num).toCharArray();
int[] lastIndex = new int[10]; // {digit: last index}

for (int i = 0; i < s.length; ++i)
lastIndex[s[i] - '0'] = i;

for (int i = 0; i < s.length; ++i)
for (int d = 9; d > s[i] - '0'; --d)
if (lastIndex[d] > i) {
s[lastIndex[d]] = s[i];
s[i] = (char) ('0' + d);
return Integer.parseInt(new String(s));
}

return num;
}
}
``````

## Python

``````class Solution:
def maximumSwap(self, num: int) -> int:
s = list(str(num))
dict = {c: i for i, c in enumerate(s)}

for i, c in enumerate(s):
for digit in reversed(string.digits):
if digit <= c:
break
if digit in dict and dict[digit] > i:
s[i], s[dict[digit]] = digit, s[i]
return int(''.join(s))

return num
``````