Problem Description

You are given a string num that represents a large integer and an array change of length 10. The array change maps each digit 0-9 to another digit - specifically, digit d maps to digit change[d].

Your task is to maximize the value of the integer by mutating at most one contiguous substring of num. When you mutate a substring, you replace each digit in that substring with its corresponding mapped value from the change array. For example, if a digit in the substring is 3 and change[3] = 7, then 3 becomes 7.

The key constraints are:

• You can only mutate a single contiguous substring (or choose not to mutate at all)
• The substring must be contiguous - you cannot skip digits in between

The goal is to return the largest possible integer (as a string) after performing this operation.

For example, if num = "132" and change = [9,8,5,0,3,6,4,2,6,8]:

• You could mutate the substring "13" to get "985" (since change[1] = 8 and change[3] = 0, but that would give "802")
• You could mutate just "1" to get "832" (since change[1] = 8)
• You could mutate just "3" to get "102" (since change[3] = 0)
• The optimal choice would be to mutate "1" to get "832"

The greedy approach works by starting from the leftmost digit and beginning mutation when we find a digit that can be improved (where change[digit] > digit). We continue the mutation as long as the mapped values are not worse than the original digits, and stop as soon as we encounter a mapped value that would decrease the digit value.

Intuition

To maximize a number, we want the leftmost (most significant) digits to be as large as possible since they contribute the most to the overall value. For instance, in the number 532, changing the first digit 5 to 9 gives us 932, which is a much larger increase than changing the last digit 2 to 9 to get 539.

Since we can only mutate one contiguous substring, we need to be strategic about when to start and stop our mutation. The key insight is that once we start mutating, we should continue as long as it doesn't make the number smaller.

Think of it this way: as we scan from left to right, we're looking for our first opportunity to improve a digit (where change[digit] > digit). Once we find such a digit, we start our mutation. But when should we stop?

We should continue the mutation as long as:

1. The changed digit is greater than the original (change[digit] > digit), OR
2. The changed digit equals the original (change[digit] == digit)

We stop immediately when we encounter a digit where change[digit] < digit because continuing would make our number smaller.

Why include the case where change[digit] == digit? Because we want our substring to be contiguous. If we skip a digit in the middle, we break the substring requirement. By including equal mappings, we maintain the contiguous property while potentially reaching more profitable digits later in the substring.

This greedy strategy works because:

• We maximize the leftmost possible digits first (highest impact on the final value)
• We take the longest beneficial substring starting from our first improvement
• We never need to consider multiple separate substrings since we can only mutate one substring total

The changed flag in the solution tracks whether we've started our mutation. Once changed becomes true, we're committed to our substring, and we can only extend it or stop it, but we cannot start a new one elsewhere.

Learn more about Greedy patterns.

Solution Approach

The implementation follows a greedy strategy with a single pass through the string:

1. Convert string to mutable structure: First, we convert the input string num into a list s since strings are immutable in Python. This allows us to modify individual characters in-place.

2. Initialize tracking variable: We use a boolean flag changed = False to track whether we've started mutating the substring. This is crucial because we can only mutate one contiguous substring.

3. Iterate through each digit: We traverse the character array s from left to right using enumeration to get both the index i and character c.

4. For each digit, apply the transformation logic:

   • Convert the current character to its mapped value: d = str(change[int(c)])
   • Check if we should stop: If we've already started changing (changed == True) and the mapped value is less than the original (d < c), we break immediately. This ensures we don't make our number smaller once we've started the mutation.
   • Check if we should change: If the mapped value is greater than the original (d > c), we:
     • Set changed = True to mark that we've started our mutation
     • Replace s[i] = d to perform the actual mutation
   • Note: If d == c, we neither break nor explicitly change anything, allowing the substring to continue if we've already started changing.

5. Return the result: Finally, join the character array back into a string using "".join(s) and return it.

The algorithm's time complexity is O(n) where n is the length of the input string, as we make a single pass through the string. The space complexity is also O(n) for storing the character array.

The key insight is that the greedy approach works because:

• We process digits from most significant to least significant
• We start changing at the first opportunity to improve
• We continue the substring as long as it doesn't decrease the value
• We stop immediately when continuing would make the number smaller

Example Walkthrough

Let's walk through the solution with num = "214" and change = [5,7,8,9,1,3,2,6,0,4].

Initial Setup:

• Convert string to list: s = ['2', '1', '4']
• Set changed = False

Step 1: Process digit '2' at index 0

• Current character: c = '2'
• Mapped value: d = str(change[2]) = str(8) = '8'
• Check conditions:
  • We haven't started changing yet (changed == False)
  • Is '8' > '2'? Yes!
• Actions:
  • Set changed = True (we've started our mutation)
  • Replace s[0] = '8'
• Current state: s = ['8', '1', '4'], changed = True

Step 2: Process digit '1' at index 1

• Current character: c = '1'
• Mapped value: d = str(change[1]) = str(7) = '7'
• Check conditions:
  • We've already started changing (changed == True)
  • Is '7' < '1'? No
  • Is '7' > '1'? Yes!
• Actions:
  • Replace s[1] = '7'
• Current state: s = ['8', '7', '4'], changed = True

Step 3: Process digit '4' at index 2

• Current character: c = '4'
• Mapped value: d = str(change[4]) = str(1) = '1'
• Check conditions:
  • We've already started changing (changed == True)
  • Is '1' < '4'? Yes! This would make our number smaller
• Actions:
  • Break immediately (stop the mutation here)
• Final state: s = ['8', '7', '4']

Result:

• Join the array: "".join(s) = "874"
• We mutated the substring "21" to "87", keeping the last digit "4" unchanged
• The original number "214" became "874", which is the maximum possible value

The key insight: We started mutating when we found our first improvement (2→8), continued when the next digit also improved (1→7), but stopped before the third digit since changing it would decrease the value (4→1). This greedy approach ensures we get the maximum possible number.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n), where n is the length of the string num.

The algorithm iterates through the string once using a single for loop. In each iteration, it performs constant-time operations:

• Converting a character to an integer: O(1)
• Accessing an element in the change list: O(1)
• String comparison and assignment: O(1)

Since we iterate through all n characters at most once, the overall time complexity is O(n).

Space Complexity: O(n), where n is the length of the string num.

The space complexity comes from:

• Converting the input string to a list: s = list(num) creates a new list of size n, which requires O(n) space
• The final string construction: "".join(s) creates a new string of size n, which requires O(n) space
• Other variables (changed, i, c, d) use constant space: O(1)

Therefore, the total space complexity is O(n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Not handling equal digits correctly during mutation

The most common mistake is breaking the mutation when change[digit] == digit. This causes the algorithm to stop prematurely and miss opportunities to improve subsequent digits in the substring.

Example of the pitfall:

# Incorrect implementation
for index, current_digit in enumerate(digit_list):
    replacement_digit = str(change[int(current_digit)])
  
    if has_started_changing and replacement_digit <= current_digit:  # Wrong!
        break
  
    if replacement_digit > current_digit:
        has_started_changing = True
        digit_list[index] = replacement_digit

With num = "214" and change = [9,8,1,0,3,6,4,2,6,8]:

• At position 0: 2 → 1 (skip, since 1 < 2)
• At position 1: 1 → 8 (change, set has_started_changing = True)
• At position 2: 4 → 3 (should stop here, but with <= we'd stop even if it was 4 → 4)

The problem occurs when the change array maps a digit to itself. If we use <= instead of <, we would incorrectly stop the mutation when encountering equal values, potentially missing better improvements later in the substring.

Pitfall 2: Starting mutation too eagerly without considering the full substring potential

Another subtle issue is not recognizing that sometimes it's better to skip early improvement opportunities to capture a longer, more valuable substring later.

Example scenario:

num = "521"
change = [9,8,5,0,3,6,4,2,6,8]

The greedy approach would:

• See 5 → 5 (no change)
• See 2 → 5 (improvement! start changing)
• See 1 → 8 (continue changing)
• Result: "558"

However, if we had skipped the first opportunity and started at position 2:

• Skip 5 and 2
• Change only 1 → 8
• Result: "528"

"558" is actually better, but this illustrates that the algorithm's correctness relies on the leftmost-first greedy strategy being optimal.

Solution to avoid these pitfalls:

1. For the equality issue: Always use strict inequality (<) when checking whether to stop, not less-than-or-equal (<=). This allows the mutation to continue through digits that map to themselves.

2. For the greedy strategy: Trust that starting at the first improvement opportunity is optimal for maximizing the numeric value. The leftmost digits have the highest place values, so improving them first yields the best result.

Correct implementation pattern:

if has_started_changing and replacement_digit < current_digit:
    break  # Stop only when the replacement would decrease the value

This ensures the mutation continues through equal mappings and only stops when it would actually make the number smaller.