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. More formally, digit d maps to digit change[d].
You may choose to mutate a single substring of num. To mutate a substring, replace each digit num[i] with the digit it maps to in change (i.e. replace 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.
A substring is a contiguous sequence of characters within the string.
Example 1:
Input: num = "132", change = [9,8,5,0,3,6,4,2,6,8] Output: "832" Explanation: Replace the substring "1": - 1 maps to change[1] = 8. Thus, "132" becomes "832". "832" is the largest number that can be created, so return it.
Example 2:
Input: num = "021", change = [9,4,3,5,7,2,1,9,0,6] Output: "934" Explanation: Replace the substring "021": - 0 maps to change[0] = 9. - 2 maps to change[2] = 3. - 1 maps to change[1] = 4. Thus, "021" becomes "934". "934" is the largest number that can be created, so return it.
Example 3:
Input: num = "5", change = [1,4,7,5,3,2,5,6,9,4] Output: "5" Explanation: "5" is already the largest number that can be created, so return it.
Constraints:
1 <= num.length <= 105num consists of only digits 0-9.change.length == 100 <= change[d] <= 9Problem 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.
The key idea is to identify a starting point where mutating will increase the number and continue mutating while the mutation continues to increase the number. Once the mutation starts decreasing the number, stop mutating.
Using a greedy strategy helps in efficiently finding this optimal point where the mutated number is larger than the original.
This C code reads a string num representing a number and an array change. It iterates through each character of the string, checking if changing it according to change results in a larger number. If a larger number is formed, it continues replacing until no further beneficial change can be made.
Time Complexity: O(n), where n is the length of the string num.
Space Complexity: O(1), since the operation is in-place.
This approach involves using two pointers to carefully choose the optimal substring to mutate. By determining the longest sequence from a potential starting point where mutation increases the number, this method extends the efficiency of the previous method for better clarity and handling.
This C code follows the two-pointer logic by first scanning the string until it finds an advantageous mutation point. The second loop directly performs the mutation until no advantageous mutation can be made, effectively maximizing the substring change.
Time Complexity: O(n).
Space Complexity: O(1), as it operates in-place.
According to the problem description, we can start from the highest digit of the string and greedily perform continuous replacement operations until we encounter a digit smaller than the current digit.
First, we convert the string num into a character array s and use a variable changed to record whether a change has already occurred, initially changed = false.
Then we traverse the character array s. For each character c, we convert it to a number d = change[int(c)]. If a change has already occurred and d < c, it means we cannot continue changing, so we exit the loop immediately. Otherwise, if d > c, it means we can replace c with d. At this point, we set changed = true and replace s[i] with d.
Finally, we convert the character array s back to a string and return it.
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the string num.
Python
Java
C++
Go
TypeScript
Rust
JavaScript
| Approach | Complexity |
|---|---|
| Greedy Approach | Time Complexity: O(n), where n is the length of the string |
| Two-Pointer Approach | Time Complexity: O(n). |
| Greedy | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy Mutation Window | O(n) | O(1) | Best general solution. Single pass, minimal logic, commonly expected in interviews. |
| Two-Pointer Expansion | O(n) | O(1) | Useful when reasoning about substring boundaries or implementing window-based logic. |
LeetCode 1946. Largest Number After Mutating Substring | 🏆 Weekly Contest 251 | Explained • Cherry Coding [IIT-G] • 874 views views
Watch 6 more video solutions →Practice Largest Number After Mutating Substring with our built-in code editor and test cases.
Practice on FleetCode