Problem statement

https://leetcode.com/problems/largest-number-after-mutating-substring/

Solution

Not difficult problem, but we need to understand what is asked, it is not very clear: the goal is to replace some substring of string, given rules, such that we have the maximum possible number (string). The idea is to use greedy strategy, where we try to replace digit by digit starting from the left. Once we start to replace digits, if at some moment we want to stop, we need to break: we can only replace adjacent substring. For this reason we have flag started.

Complexity

Time and space complexity is O(n).

Code

class Solution:
    def maximumNumber(self, num, C):
        l, started = [int(i) for i in num], False
        for i, dig in enumerate(l): 
            if dig < C[dig]: 
                started = True
                l[i] = C[dig]
            if dig > C[dig] and started: break 
        return "".join(str(i) for i in l)