670. Maximum Swap - cocoder39/coco39_LC GitHub Wiki

670. Maximum Swap

At each digit of the input number in order, if there is a larger digit that occurs later, we know that the swap with the larger digit can make the number bigger:

• the larger digit to swap with, the bigger the number will be (eg, 123 -> 321)
• if there are multiple largest digit (eg, 1939), swap with the right most one (9931)

greedy:

• 1. we start from the left most digit to see if there is a good candidate in the right that can make the entire number bigger
• 2. when considering candidates, we can count down from 9

Optimization of step 2: we pre-process the number to store the mapping from each of the 9 digits to the last index it presents

237838 -> 837832

class Solution:
    def maximumSwap(self, num: int) -> int:
        digits = list(str(num))
        print(digits)
        last_index = {int(digit): i for i, digit in enumerate(digits)}
        
        for i, digit in enumerate(digits):
            for replacement in range(9, int(digit), -1):
                if replacement in last_index and last_index[replacement] > i:
                    j = last_index[replacement]
                    digits[i], digits[j] = digits[j], digits[i]
                    return int(''.join(digits))
        
        return num