Problem statement

https://leetcode.com/problems/maximum-swap/

Solution

There is O(n^3) brute-force solution.

There is also O(9n) solution: let us first find last places for each digit in O(n). Then let us start from the first digit and find if we have 9 after it, if we have 8 after it and so on. Then we go to the second digit and continue. Space complexity is O(n).

There is also just O(n) solution (without constant 9), where we for each place keep dp[i] be the largest digit starting from place i: we fill this array from the end. The second part of algorithm is the same.

Complexity

It is O(n) for time and O(n) for space where n is number of digits in num.

Code

class Solution:
    def maximumSwap(self, num):
        D = list(str(num))
        dp = list(accumulate(D[::-1], max))[::-1]
        
        for i, digit in enumerate(D):
            if dp[i] > digit:
                for k in range(i, len(D)):
                    if D[k] == dp[i]: j = k     
                D[i], D[j] = D[j], D[i]
                return "".join(D)
        
        return num