Largest Number After Mutating Substring — Problem & Solution
Largest Number After Mutating Substring solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Largest Number After Mutating Substring is a medium coding problem on arrays, strings and greedy, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Arrays, Strings, Greedy
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
num is a large integer written as a string of digits, and change is an array of 10 digits that maps each digit d to change[d].
You may mutate one contiguous substring of num — replace every digit d in it by change[d] — or leave num unchanged. Return the largest integer you can obtain, as a string.
Example 1
Input: num = "214", change = [0,1,9,3,4,5,6,7,8,9]
Output: 914
Explanation: Mutating just the first digit turns 2 into 9.
Example 2
Input: num = "5", change = [1,4,7,5,3,2,5,6,9,4]
Output: 5
Explanation: 5 would become 2, so it is better not to mutate anything.
Example 3
Input: num = "3809", change = [0,1,2,7,4,5,6,7,5,9]
Output: 7809
Explanation: 3 becomes 7, but extending the substring over the 8 would turn it into a 5.
Constraints
1 <= num.length <= 10^5num consists of digits onlychange.length == 100 <= change[d] <= 9
Hints for Largest Number After Mutating Substring
Hint 1
All results have the same length, so the leftmost digit you can raise matters more than everything after it.
Hint 2
Start the substring at the first digit
dwithchange[d] > d.Hint 3
Then keep extending while
change[d] >= dand stop at the first digit that would get smaller.
How to solve Largest Number After Mutating Substring
Numbers of equal length compare like strings, so raise the leftmost digit that can be raised, then keep mutating for as long as no digit gets worse.
Approach
- Scan for the first index
iwhose digitdhaschange[d] > d. If there is none, returnnumunchanged. - From
i, replace each digitdbychange[d]whilechange[d] >= d. - Stop at the first digit with
change[d] < d(or the end) and return the result.
Why it works
Any mutation that leaves the first improvable position i untouched cannot beat one that raises it: positions before i can only stay equal or drop, and raising position i wins the comparison there. Once started at i, extending over a digit that stays equal or grows never hurts, while including a digit that shrinks makes the number smaller at that position — and since the substring must be contiguous, nothing after it can be mutated anyway.
Complexity
- Time —
O(n) - Space —
O(n) for the output string
Pitfalls
- Digits with
change[d] == dmust not start the substring (it gains nothing) but must not stop it either. - Only one substring may be mutated: do not resume after stopping.
- Mutating nothing is allowed — return
numwhen no digit improves.
Reference solution
Python
from typing import List
def maximumNumber(num: str, change: List[int]) -> str:
digits = list(num)
n = len(digits)
i = 0
while i < n and change[int(digits[i])] <= int(digits[i]):
i += 1
while i < n and change[int(digits[i])] >= int(digits[i]):
digits[i] = str(change[int(digits[i])])
i += 1
return ''.join(digits)Java
public static String maximumNumber(String num, int[] change) {
char[] digits = num.toCharArray();
int n = digits.length, i = 0;
while (i < n && change[digits[i] - '0'] <= digits[i] - '0') i++;
while (i < n && change[digits[i] - '0'] >= digits[i] - '0') {
digits[i] = (char) ('0' + change[digits[i] - '0']);
i++;
}
return new String(digits);
}C++
string maximumNumber(string num, vector<int>& change) {
int n = num.size(), i = 0;
while (i < n && change[num[i] - '0'] <= num[i] - '0') i++;
while (i < n && change[num[i] - '0'] >= num[i] - '0') {
num[i] = (char)('0' + change[num[i] - '0']);
i++;
}
return num;
}JavaScript
var maximumNumber = function(num, change) {
var digits = num.split("");
var n = digits.length, i = 0;
while (i < n && change[+digits[i]] <= +digits[i]) i++;
while (i < n && change[+digits[i]] >= +digits[i]) {
digits[i] = String(change[+digits[i]]);
i++;
}
return digits.join("");
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.