Scale Engineer

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
ArrayString
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 <= 105
  • 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.

class Solution {    public String maximumNumber(String num, int[] change) {        String maxNum = num;        int n = num.length();         // Iterate over all possible start indices of the substring        for (int i = 0; i < n; i++) {            // Iterate over all possible end indices of the substring            for (int j = i; j < n; j++) {                // Create a temporary array for mutation for the current substring                char[] currentNumArr = num.toCharArray();                                // Mutate the substring from i to j                for (int k = i; k <= j; k++) {                    int digit = currentNumArr[k] - '0';                    currentNumArr[k] = (char) (change[digit] + '0');                }                                String mutatedNum = new String(currentNumArr);                                // Compare the new number with the current maximum found so far                // String comparison works for large numbers as it's lexicographical                if (mutatedNum.compareTo(maxNum) > 0) {                    maxNum = mutatedNum;                }            }        }        return maxNum;    }}

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.

Solutions

class 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 ); } }

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 →

Next problem