Largest Number After Mutating Substring

To solve this problem, the steps are:

1. Traverse through the num string.
2. If change[num[i]] > num[i], this means we can change num[i] to a bigger value. This is the beginning of the substring to mutate.
3. Keep mutating while change[num[i]] >= num[i]. This is to maximize the number. Notice the equality here because if they are equal, we continue replacing (even though there is no change) to maximize the substring that can be changed. Once this condition breaks, stop mutating and append the rest of the original string.
4. If we haven’t started mutating till the end of num, simply return num as no beneficial mutation is possible.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution:
    def maximumNumber(self, num: str, change: List[int]) -> str:
        mutated = False  # To check if we started mutation
        result = []

        i = 0
        while i < len(num):
            # Check if the current digit can be replaced with a bigger value and if mutation hasn't started yet
            if not mutated and change[int(num[i])] > int(num[i]):
                mutated = True
                while i < len(num) and change[int(num[i])] >= int(num[i]):
                    result.append(str(change[int(num[i])]))
                    i += 1
            else:
                result.append(num[i])
                i += 1
        
        return ''.join(result)

This approach goes through the num string once and checks each digit against the change list, so the time complexity is O(n), where n is the length of the num string.