Largest Number After Mutating Substring: Greedy Digit Replacement

You are given a string num representing a large integer and an array change of length 10, where change[d] is the digit that d can be replaced with. You may pick one contiguous substring and replace every digit d in it with change[d]. Return the largest possible number you can create. This is LeetCode 1946: Largest Number After Mutating Substring.

The problem

Given num = "132" and change = [9,8,5,0,3,6,4,2,6,8], you can choose a contiguous substring and replace each digit d with change[d]. The goal is to maximize the resulting number.

For digit 1, change[1] = 8, so replacing it gives a gain (8 > 1). For digit 3, change[3] = 0, so replacing it would make the number smaller (0 < 3). For digit 2, change[2] = 5, so replacing it gives a gain (5 > 2). But because the substring must be contiguous, once you stop mutating, you cannot start again. The best choice is to replace only the substring at index 0, turning "132" into "832".

The approach

The key insight is that you want to maximize the leftmost digits first. A greedy left-to-right scan handles this naturally.

Scan the digits from left to right. At each position, check whether change[d] is greater than or equal to the current digit d. If it is strictly greater, you have found a digit worth replacing, so you start (or continue) mutating. If it is equal, you can continue mutating without loss. If it is strictly less than d, you must stop. Once you stop mutating, you break out of the loop, because any further mutation would require a gap in the substring.

There are three phases:

1. Before mutating: skip digits where change[d] is less than or equal to d, since replacing them would not help (and for equal digits, there is no reason to start a mutation window).
2. While mutating: replace each digit d with change[d] as long as change[d] is greater than or equal to d. Equal digits keep the mutation window open because stopping prematurely might miss a beneficial replacement later.
3. After stopping: once change[d] is strictly less than d during mutation, stop immediately. Do not mutate any more digits.

This greedy strategy works because digits to the left carry more weight. Replacing a digit at position 0 with a larger value always beats replacing a digit at position 5.

Visual walkthrough

The scan found that digit 1 at index 0 benefits from mutation (change[1] = 8 > 1), so it started mutating. At index 1, digit 3 would be replaced with change[3] = 0, which is worse, so the mutation stopped. The final result is "832".

The code

def maximum_number(num, change):
    num = list(num)
    mutating = False
    for i in range(len(num)):
        d = int(num[i])
        if change[d] > d:
            mutating = True
            num[i] = str(change[d])
        elif change[d] < d and mutating:
            break
    return "".join(num)

The function converts the string to a list for mutability. It scans left to right, tracking whether mutation has started.

• d = int(num[i]) gets the current digit.
• If change[d] > d, this digit benefits from replacement. Set mutating = True and replace the digit.
• If change[d] < d and we are already mutating, we have hit a digit that would get worse. Break out of the loop.
• If change[d] == d, we leave the digit as-is but do not stop mutating if we have already started. The mutation window stays open.
• If change[d] < d and we have not started mutating yet, we simply skip this digit and keep scanning.

Complexity analysis

The algorithm makes a single pass through the string, so time is O(n). The space is O(n) because we convert the string to a list. If the language supports mutable strings, space could be O(1), but Python strings are immutable.

Building blocks

1. Greedy left-to-right scan

The core pattern here is scanning from the most significant position to the least significant, making locally optimal decisions. Because leftmost digits have the most impact on the number's value, processing left to right guarantees a globally optimal result. This same pattern appears in problems like creating the largest number from array elements or finding the next permutation.

2. Contiguous window with entry and exit conditions

The mutation window behaves like a sliding window with a specific start condition (find a beneficial digit) and stop condition (find a harmful digit). Unlike classic sliding windows that might shrink from the left, this window only expands rightward and closes permanently. This "one-shot window" pattern shows up whenever you need to find the best contiguous segment under a monotonic constraint.

Edge cases

• All digits benefit from mutation: every change[d] is greater than or equal to d. The entire string gets mutated. For example, num = "000", change = [9,9,9,9,9,9,9,9,9,9] becomes "999".
• No digits benefit: every change[d] is less than or equal to d. No mutation happens and the original number is returned unchanged.
• Equal mappings: if change[d] == d for some digit, replacing it has no effect. The algorithm correctly continues the mutation window through equal digits without breaking.
• Single-digit number: the algorithm still works. If change[d] > d, replace it. Otherwise, return it as-is.

From understanding to recall

You have walked through the greedy scan and it clicks. Scan left to right, start replacing when you find a digit that benefits, keep going through equal or better digits, stop the moment a replacement would hurt. Simple enough on paper. But writing it from scratch under interview pressure is a different challenge.

The tricky part is the three-way branching: strictly greater starts or continues mutation, equal continues but does not start, strictly less stops mutation or gets skipped. Getting these conditions wrong is the most common mistake. Spaced repetition locks in these details so you do not second-guess yourself during the interview.

Related posts

• Gas Station - Another greedy problem about finding optimal starting points
• Jump Game - Greedy approach to determine reachability
• Container With Most Water - Greedy two-pointer technique