BinarySearch 0751 Maximum Number After One Swap

Problem statement

https://binarysearch.com/problems/Maximum-Number-After-One-Swap/

Solution

Equal to Leetcode 0670 Maximum Swap.

Complexity

It is true O(n) for time and space (true, means, without factor 9).

Code

class Solution:
    def solve(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 int("".join(D))
        
        return int(num)