#1946

Medium

auto_awesomeGreedy choice plus invariant validation

LeetCode Problem Workspace

Largest Number After Mutating Substring

Find the largest integer by mutating a substring of a number using a mapping array for each digit.

Problem Statement

Given a string num representing a large integer and an integer array change of length 10 that maps each digit 0-9 to another digit, you can mutate a substring of num by replacing each digit with its corresponding digit in change. The objective is to find the largest integer possible after mutating at most one substring of num.

Return the mutated string as the largest possible number. If no mutation improves the number, the original num should be returned.

Examples

Example 1

Input: num = "132", change = [9,8,5,0,3,6,4,2,6,8]

Output: "832"

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"

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"

"5" is already the largest number that can be created, so return it.

Constraints

1 <= num.length <= 105
num consists of only digits 0-9.
change.length == 10
0 <= change[d] <= 9

Solution Approach

Greedy Mutation Strategy

Start by identifying the first point where a digit in num can be changed to a larger value using the mapping. Mutate the substring starting at that point and continue until no further beneficial mutations are possible.

Breaking Early with Validation

If a mutation leads to a smaller digit than the original, stop making further changes. This is the invariant: we must not choose smaller digits even if they appear later in the number.

Efficient Iteration

Iterate through the number once, applying the mutation only to the digits that increase the value, ensuring a time complexity of O(n) with minimal space usage.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity is O(n) due to the single pass through the string num, where n is the length of the string. The space complexity is O(1) since no additional data structures are required beyond the input arrays.

What Interviewers Usually Probe

Evaluating the candidate's ability to apply a greedy strategy in a non-trivial mutation problem.
Checking for understanding of early stopping and its importance in optimizing the solution.
Assessing the candidate's grasp of the pattern behind the greedy approach and its validation.

Common Pitfalls or Variants

Common pitfalls

Failing to stop mutating when the result becomes smaller than the original number.
Not recognizing that changing digits in the middle of the number can lead to smaller results if not carefully handled.
Mutating a digit even when it doesn’t improve the value, leading to unnecessary changes.

Follow-up variants

Allowing multiple substrings to mutate instead of just one.
Different variations of the mapping where some digits map to the same value.
Adding conditions like not allowing leading zeros after mutation.

FAQ

What is the main approach to solving the Largest Number After Mutating Substring problem?

The main approach is to use a greedy algorithm where you apply the mutation to a substring that maximizes the result while avoiding any mutations that result in smaller digits.

Why is it important to stop mutating when a digit becomes smaller?

Stopping prevents making changes that decrease the number's value, ensuring you only make mutations that improve or maintain the result.

How do you know where to stop mutating in the number?

You should stop mutating once you encounter a digit where its mapped value is smaller than the original. Further mutations would only decrease the number.

What happens if the number is already the largest possible without mutations?

If the number is already the largest possible, no mutation is applied, and the original number is returned as the result.

Can I mutate multiple substrings in this problem?

The problem restricts you to mutating only one substring of the number to achieve the largest possible result.

terminal

Solution

Solution 1: Greedy

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.

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def maximumNumber(self, num: str, change: List[int]) -> str:
        s = list(num)
        changed = False
        for i, c in enumerate(s):
            d = str(change[int(c)])
            if changed and d < c:
                break
            if d > c:
                changed = True
                s[i] = d
        return "".join(s)

Continue Practicing

#2131 longest palindrome by concatenating two letter words #1578 minimum time to make rope colorful #2573 find the string with lcp