Largest Number After Mutating Substring - Video Solutions

Problem Overview: You are given a numeric string num and an array change where each digit d can be replaced with change[d]. You may choose one contiguous substring and mutate its digits using this mapping. The goal is to produce the lexicographically largest possible number.

Approach 1: Greedy Mutation Window (O(n) time, O(1) space)

The optimal strategy is greedy. Scan the string from left to right and look for the first position where mutating the digit increases its value (change[d] > d). Once you start mutating, continue replacing digits while the mapped value is greater than or equal to the original digit. If the mapped digit becomes smaller, stop the mutation immediately because extending the substring would reduce the number. This works because earlier digits contribute more to the overall value of the number, so maximizing the leftmost improvable position yields the best result. The algorithm performs a single pass through the string and mutates digits in place.

This greedy observation avoids trying multiple substrings. Instead of exploring combinations, you simply expand the first profitable mutation segment and stop once the replacement no longer helps. Time complexity is O(n) since each digit is processed once, and space complexity is O(1) aside from the output string. The technique is a classic greedy decision pattern often seen in greedy optimization problems involving string manipulation.

Approach 2: Two-Pointer Expansion (O(n) time, O(1) space)

You can also view the problem as identifying a mutation window using two pointers. First pointer scans for the starting index where replacing a digit improves the value (change[d] > d). Once found, a second pointer expands the substring while replacements do not decrease the digit (change[d] >= d). During this expansion, replace digits directly in the result string. When the condition fails, stop the window and return the final number.

This approach expresses the same logic using explicit window boundaries. The left pointer marks the first beneficial mutation, and the right pointer grows the substring while the mapping remains non-decreasing. It’s useful if you want to reason about substring boundaries or implement the logic in languages where window-style iteration is clearer. Complexity remains O(n) time and O(1) extra space since each character is visited at most once.

Recommended for interviews: The greedy single-pass approach is what most interviewers expect. It shows that you understand how lexicographic maximization works and why starting mutation at the earliest beneficial index is optimal. Explaining the reasoning—start when change[d] > d, continue while change[d] >= d, stop when it becomes smaller—demonstrates strong problem-solving intuition with array-based digit mappings.