Largest Number After Mutating Substring

Problem Description

You are given a string num, which represents a large integer. You are also given a 0-indexed integer array change of length 10 that maps each digit 0-9 to another digit. You may choose to mutate a single substring of num by replacing each digit num[i] with change[num[i]]. Return a string representing the largest possible integer after mutating (or choosing not to) a single substring of num.

Key Insights

• A substring can be mutated by replacing each digit with its corresponding value from the change array.
• The goal is to maximize the resultant number after potentially mutating a continuous section of num.
• The mutation should start when we find a digit that can be changed to a larger digit and can continue until we reach a digit that should not be mutated.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

The approach involves a single pass through the string num. We will iterate through each character and check if it can be mutated to a larger digit using the change array. If we encounter a digit that can be mutated to a larger value, we start mutating until we reach a digit that cannot be improved. After the mutation process, we concatenate the parts together to form the final result.

1. Iterate through the string num.
2. If the digit at the current position can be mutated to a larger digit, start a mutation process.
3. Continue the mutation until a digit that should not be mutated is encountered.
4. Return the result as a string.

Code Solutions