# Largest Number After Mutating Substring
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/largest-number-after-mutating-substring)
Canonical: https://scaleengineer.com/dsa/problems/largest-number-after-mutating-substring
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** Array, String
**Companies:** [Infosys](https://scaleengineer.com/companies/infosys)
---
## Problem
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
## Brute-Force by Checking All Substrings
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.
**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.
**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.
### Explanation
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.

```java
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;
    }
}
```
### 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.

## Single-Pass Greedy Approach
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.
**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).
**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.
### Explanation
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.

```java
class Solution {
    public String maximumNumber(String num, int[] change) {
        char[] numArray = num.toCharArray();
        int n = numArray.length;
        boolean startedMutation = false;

        for (int i = 0; i < n; i++) {
            int digit = numArray[i] - '0';
            int newDigit = change[digit];

            if (newDigit > digit) {
                // This is a beneficial change. Start or continue mutating.
                numArray[i] = (char) (newDigit + '0');
                startedMutation = true;
            } else if (newDigit == digit) {
                // No change in value, continue the current mutation if it has started.
                // No action needed if mutation hasn't started.
                continue;
            } else { // newDigit < digit
                // This is a detrimental change.
                // If we have started a mutation, we must stop here.
                if (startedMutation) {
                    break;
                }
                // If mutation hasn't started, we just continue to the next digit.
            }
        }

        return new String(numArray);
    }
}
```
An alternative implementation of the same logic separates finding the start and performing the mutation:
```java
class Solution {
    public String maximumNumber(String num, int[] change) {
        char[] numArray = num.toCharArray();
        int n = numArray.length;
        int start = -1;

        // 1. Find the first digit that can be improved
        for (int i = 0; i < n; i++) {
            int digit = numArray[i] - '0';
            if (change[digit] > digit) {
                start = i;
                break;
            }
        }

        // If no improvement is possible, return original number
        if (start == -1) {
            return num;
        }

        // 2. From the start, mutate as long as it's not detrimental
        for (int i = start; i < n; i++) {
            int digit = numArray[i] - '0';
            if (change[digit] >= digit) {
                numArray[i] = (char) (change[digit] + '0');
            } else {
                // Stop when mutation becomes detrimental
                break;
            }
        }

        return new String(numArray);
    }
}
```
### 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.

# Solutions
### Java

```java
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 ); } }
```

### JavaScript

```javascript
/** * @param {string} num * @param {number[]} change * @return {string} */ var maximumNumber =
  function (num, change) {
    const s = num.split("");
    let changed = false;
    for (let i = 0; i < s.length; ++i) {
      const d = change[+s[i]].toString();
      if (changed && d < s[i]) {
        break;
      }
      if (d > s[i]) {
        s[i] = d;
        changed = true;
      }
    }
    return s.join("");
  };

```

### CPP

```cpp
class 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 ; } };
```

### Python

```python
class 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 )
```