'''
https://leetcode.com/problems/maximum-swap/
2021/10
32 ms
'''

class Solution:
    def maximumSwap(self, num: int) -> int:
        num_, idx, digits, p_last = num, 0, [], {x: 2000 for x in range(0, 10)}
        while num_ > 0:
            d = num_ % 10
            num_ //= 10
            digits.append(d)
            p_last[d] = min(p_last[d], idx)
            idx += 1
        for x in range(0, 10)[::-1]:
            p = p_last[x]
            if p < 1000:
                for p2 in range(p + 1, len(digits))[::-1]:
                    if digits[p2] < x:
                        x2 = digits[p2]
                        num -= x2 * (10 ** p2) + x * (10 ** p)
                        num += x * (10 ** p2) + x2 * (10 ** p)
                        return num
        return num
