Largest Number After Mutating Substring

Med

#1775Time: O(N^3), where N is the length of `num`. There are O(N^2) possible substrings. For each substring, creating the new mutated string by copying and then modifying it takes O(N) time. Comparing the resulting O(N)-length string with the current maximum also takes O(N). This leads to a total complexity of O(N^2 * N) = O(N^3).Space: O(N), where N is the length of `num`. In each iteration of the inner loop, we create a `char[]` of size N to represent the mutated number. The `maxNum` string also requires O(N) space.1 company

Patterns

Greedy

Data structures

Array String

Companies

Infosys

Prompt

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 <= 10⁵
num consists of only digits 0-9.
change.length == 10
0 <= change[d] <= 9

Approaches

2 approaches with complexity analysis and trade-offs.

This approach exhaustively checks every possible substring of the input number num. For each substring, it performs the mutation and compares the resulting number with the largest number found so far. This guarantees finding the optimal solution but is computationally expensive.

Algorithm

Initialize a string maxNum to the original num. This handles the case where no mutation is performed or no mutation leads to a larger number.
Use nested loops to iterate through all possible start indices i (from 0 to n-1) and end indices j (from i to n-1), where n is the length of num.
For each pair (i, j), create a new candidate number by mutating the substring num[i...j].
To do this, we can convert num to a character array. Then, iterate from k = i to j and replace the character at index k with its mapped value from the change array.
Convert the modified character array back to a string.
Compare this new string with maxNum. If it's lexicographically larger, update maxNum.
After all substrings have been processed, maxNum will hold the string representation of the largest possible integer.

Walkthrough

The core idea is to generate every possible number that can be formed by mutating a single substring and then find the maximum among them. A substring is defined by its start and end indices. We also need to consider the case of not mutating at all, which is covered by initializing our maximum with the original number.

1class Solution {2    public String maximumNumber(String num, int[] change) {3        String maxNum = num;4        int n = num.length();5 6        // Iterate over all possible start indices of the substring7        for (int i = 0; i < n; i++) {8            // Iterate over all possible end indices of the substring9            for (int j = i; j < n; j++) {10                // Create a temporary array for mutation for the current substring11                char[] currentNumArr = num.toCharArray();12                13                // Mutate the substring from i to j14                for (int k = i; k <= j; k++) {15                    int digit = currentNumArr[k] - '0';16                    currentNumArr[k] = (char) (change[digit] + '0');17                }18                19                String mutatedNum = new String(currentNumArr);20                21                // Compare the new number with the current maximum found so far22                // String comparison works for large numbers as it's lexicographical23                if (mutatedNum.compareTo(maxNum) > 0) {24                    maxNum = mutatedNum;25                }26            }27        }28        return maxNum;29    }30}

Complexity

Time

O(N^3), where N is the length of `num`. There are O(N^2) possible substrings. For each substring, creating the new mutated string by copying and then modifying it takes O(N) time. Comparing the resulting O(N)-length string with the current maximum also takes O(N). This leads to a total complexity of O(N^2 * N) = O(N^3).

Space

O(N), where N is the length of `num`. In each iteration of the inner loop, we create a `char[]` of size N to represent the mutated number. The `maxNum` string also requires O(N) space.

Trade-offs

Pros

Guaranteed to find the correct answer as it explores all possibilities.
Conceptually simple to understand and implement.

Cons

Extremely inefficient, especially for large inputs with N up to 10^5.
Results in a 'Time Limit Exceeded' (TLE) error on most platforms for the given constraints.

A much more efficient approach is to use a greedy strategy. To get the largest possible number, we want to make an improvement at the most significant (leftmost) digit possible. This approach finds the first opportunity to make a beneficial change and then extends the mutation as long as it's not detrimental.

Algorithm

First, find the starting point for the mutation. We iterate from left to right (index i) through the string num and find the first digit d = num[i] for which its mapping change[d] is strictly greater than d. Let this index be start.
If no such index is found, it means no mutation can make the number larger. Any mutation would either keep the number the same or make it smaller. In this case, the original number num is the largest possible, so we return it.
If we find such a start index, we have found the beginning of our optimal substring to mutate. We must mutate num[start].
Now, we need to determine the end of the substring. We continue iterating from start onwards (index j). We extend the mutated substring as long as the mutation is not detrimental. That is, we continue as long as for a digit d = num[j], its mapping change[d] is greater than or equal to d.
The mutation stops at the first index j where change[num[j]] < num[j].
We then mutate the single substring from start to j-1 and return the resulting string. Since strings are immutable in Java, it's efficient to convert num to a char[] or StringBuilder, perform the mutations in-place, and then convert it back to a string.

Walkthrough

The key insight is that to maximize the resulting number, any change we make should be as far to the left as possible. A change at index i is more impactful than any change at an index j > i. Therefore, we should look for the first digit from the left that we can change to a larger digit. Once we find this starting point, we should continue changing subsequent digits as long as the change is not for the worse (i.e., the new digit is smaller than the old one). If we stop mutating, we cannot start another mutation later, as we are only allowed to mutate a single substring.

1class Solution {2    public String maximumNumber(String num, int[] change) {3        char[] numArray = num.toCharArray();4        int n = numArray.length;5        boolean startedMutation = false;6 7        for (int i = 0; i < n; i++) {8            int digit = numArray[i] - '0';9            int newDigit = change[digit];10 11            if (newDigit > digit) {12                // This is a beneficial change. Start or continue mutating.13                numArray[i] = (char) (newDigit + '0');14                startedMutation = true;15            } else if (newDigit == digit) {16                // No change in value, continue the current mutation if it has started.17                // No action needed if mutation hasn't started.18                continue;19            } else { // newDigit < digit20                // This is a detrimental change.21                // If we have started a mutation, we must stop here.22                if (startedMutation) {23                    break;24                }25                // If mutation hasn't started, we just continue to the next digit.26            }27        }28 29        return new String(numArray);30    }31}

An alternative implementation of the same logic separates finding the start and performing the mutation:

1class Solution {2    public String maximumNumber(String num, int[] change) {3        char[] numArray = num.toCharArray();4        int n = numArray.length;5        int start = -1;6 7        // 1. Find the first digit that can be improved8        for (int i = 0; i < n; i++) {9            int digit = numArray[i] - '0';10            if (change[digit] > digit) {11                start = i;12                break;13            }14        }15 16        // If no improvement is possible, return original number17        if (start == -1) {18            return num;19        }20 21        // 2. From the start, mutate as long as it's not detrimental22        for (int i = start; i < n; i++) {23            int digit = numArray[i] - '0';24            if (change[digit] >= digit) {25                numArray[i] = (char) (change[digit] + '0');26            } else {27                // Stop when mutation becomes detrimental28                break;29            }30        }31 32        return new String(numArray);33    }34}

Complexity

Time

O(N), where N is the length of `num`. We perform a single pass over the string to find the mutation window and apply the changes. This results in a linear time complexity.

Space

O(N) to store the `char[]` representation of the number for mutation. In a language with mutable strings, the space complexity could be considered O(1) (in-place modification).

Trade-offs

Pros

Extremely efficient with linear time complexity.
Simple to implement once the greedy logic is understood.
Passes all test cases within the time limits.

Cons

The greedy choice might seem non-obvious at first, requiring a careful proof of correctness to be sure it covers all cases.

Solutions

Solution

1class Solution { public String maximumNumber ( String num , int [] change ) { char [] s = num . toCharArray (); for ( int i = 0 ; i < s . length ; ++ i ) { if ( change [ s [ i ] - '0' ] > s [ i ] - '0' ) { for (; i < s . length && s [ i ] - '0' <= change [ s [ i ] - '0' ]; ++ i ) { s [ i ] = ( char ) ( change [ s [ i ] - '0' ] + '0' ); } break ; } } return String . valueOf ( s ); } }

1/** * @param {string} num * @param {number[]} change * @return {string} */ var maximumNumber =2  function (num, change) {3    const s = num.split("");4    let changed = false;5    for (let i = 0; i < s.length; ++i) {6      const d = change[+s[i]].toString();7      if (changed && d < s[i]) {8        break;9      }10      if (d > s[i]) {11        s[i] = d;12        changed = true;13      }14    }15    return s.join("");16  };

1class Solution { public: string maximumNumber ( string num , vector < int >& change ) { int n = num . size (); for ( int i = 0 ; i < n ; ++ i ) { if ( change [ num [ i ] - '0' ] > num [ i ] - '0' ) { for (; i < n && change [ num [ i ] - '0' ] >= num [ i ] - '0' ; ++ i ) { num [ i ] = change [ num [ i ] - '0' ] + '0' ; } break ; } } return num ; } };

1class Solution : def maximumNumber ( self , num : str , change : List [ int ]) -> str : s = list ( num ) for i , c in enumerate ( s ): if change [ int ( c )] > int ( c ): while i < len ( s ) and int ( s [ i ]) <= change [ int ( s [ i ])]: s [ i ] = str ( change [ int ( s [ i ])]) i += 1 break return '' . join ( s )

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem