Problem statement

https://binarysearch.com/problems/Lexicographic-Swap/

Solution

General version of Leetcode 0670 Maximum Swap, where we need linear time algorithm.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def solve(self, s):
        s = [i for i in s]
        dp = list(accumulate(s[::-1], min))[::-1]
        
        for i, l in enumerate(s):
            if dp[i] < l:
                for k in range(i, len(s)):
                    if s[k] == dp[i]: j = k     
                s[i], s[j] = s[j], s[i]
                return "".join(s)
        
        return "".join(s)