Problem Description

You are given a string of digits num and an integer array change of length 10, where change[i] indicates the digit you can mutate digit i into. You can choose at most one contiguous substring of num and mutate every digit x within this substring to change[x]. Each digit in the chosen substring must be mutated (no skipping). Your goal is to return the largest possible number obtainable as a string after performing at most one such mutation.

• You must mutate a contiguous substring (possibly the whole string or a single digit).
• You can only mutate at most one substring (or none at all).
• Every digit in the chosen substring is mutated according to change.
• Return the largest possible string after mutation.

Thought Process

At first glance, one might consider brute-forcing all possible substrings and checking the result after mutating each. However, with a string of length up to 10⁵, this would be too slow.

Instead, let's think about when it's beneficial to mutate a digit. If change[digit] is greater than the original digit, mutating increases the value. If it's less, mutating decreases the value and should be avoided. If it's equal, mutating has no effect.

The best strategy is to start mutating at the first position where change[digit] > digit and continue mutating as long as change[digit] ≥ digit. We must stop as soon as change[digit] < digit to avoid decreasing the number.

This greedy approach ensures we create the largest possible number in a single pass, avoiding unnecessary mutations.

Solution Approach

• Step 1: Iterate over the string from left to right.
• Step 2: Look for the first digit d where change[d] > d. This is where we should start mutating.
• Step 3: Once started, continue mutating as long as change[d] ≥ d for each digit in the substring.
• Step 4: If you encounter a digit where change[d] < d, stop mutating. From here onward, keep the original digits.
• Step 5: Return the resulting string.

This approach is greedy and only mutates when it increases or keeps the value, and stops as soon as it would decrease the value. We only ever mutate one contiguous substring, as the problem requires.

Example Walkthrough

Consider num = "132" and change = [9,8,5,0,3,6,4,2,6,8].

1. First digit: '1'. change[1] = 8, which is greater than 1. Start mutating here.
2. Second digit: '3'. change[3] = 0, which is less than 3. Stop mutating before this digit.
3. So, only the first digit is mutated: '1' becomes '8'.
4. The rest of the string remains the same.
5. Final result: "832".

If we continued mutating after the first digit, the number would decrease, which is not optimal.

Time and Space Complexity

• Brute-force approach: For each possible substring, mutate and compare. There are O(n²) substrings, and each mutation takes O(n) time, so total O(n³) time. This is infeasible for large n.
• Optimized approach: We make a single pass through the string, mutating at most once. This is O(n) time and O(n) space (for the result string).

The greedy approach is both time and space efficient.

Summary

By analyzing when mutating digits increases the value, we use a greedy, one-pass strategy to find the largest number. We start mutating at the first opportunity and stop as soon as mutating would decrease the number. This ensures correctness and efficiency, making the solution both elegant and optimal.

Code Implementation

class Solution:
    def maximumNumber(self, num: str, change: List[int]) -> str:
        num_list = list(num)
        n = len(num)
        started = False
        for i in range(n):
            d = int(num_list[i])
            if not started:
                if change[d] > d:
                    started = True
                    num_list[i] = str(change[d])
            else:
                if change[d] >= d:
                    num_list[i] = str(change[d])
                else:
                    break
        return ''.join(num_list)
      

class Solution {
public:
    string maximumNumber(string num, vector<int>& change) {
        bool started = false;
        int n = num.size();
        for (int i = 0; i < n; ++i) {
            int d = num[i] - '0';
            if (!started) {
                if (change[d] > d) {
                    started = true;
                    num[i] = change[d] + '0';
                }
            } else {
                if (change[d] >= d) {
                    num[i] = change[d] + '0';
                } else {
                    break;
                }
            }
        }
        return num;
    }
};
      

class Solution {
    public String maximumNumber(String num, int[] change) {
        char[] arr = num.toCharArray();
        boolean started = false;
        for (int i = 0; i < arr.length; ++i) {
            int d = arr[i] - '0';
            if (!started) {
                if (change[d] > d) {
                    started = true;
                    arr[i] = (char)(change[d] + '0');
                }
            } else {
                if (change[d] >= d) {
                    arr[i] = (char)(change[d] + '0');
                } else {
                    break;
                }
            }
        }
        return new String(arr);
    }
}
      

var maximumNumber = function(num, change) {
    let arr = num.split('');
    let started = false;
    for (let i = 0; i < arr.length; ++i) {
        let d = parseInt(arr[i]);
        if (!started) {
            if (change[d] > d) {
                started = true;
                arr[i] = change[d].toString();
            }
        } else {
            if (change[d] >= d) {
                arr[i] = change[d].toString();
            } else {
                break;
            }
        }
    }
    return arr.join('');
};