Largest Number After Mutating Substring solution and explanation
Infosys
4 more videos on this problem
LeetCode 1946. Largest Number After Mutating Substring | 🏆 Weekly Contest 251 | ExplainedCherry Coding [IIT-G] · 7:48 · 902 views
Largest Number after mutating Substring Leetcode weekly contest 251 Solution easy. Leetcode Medium.CodeinDepth · 6:29 · 189 views
1946. Largest Number After Mutating Substring (Leetcode Medium)Programming Live with Larry · 13:32 · 179 views
Largest Number After Mutating SubstringOwen Wu · 5:31 · 13 views
LeetCode 1946: Largest Number After Mutating SubstringAlitaCode · 22:23 · 3 views
The 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 <= 105numconsists of only digits0-9.change.length == 100 <= change[d] <= 9
Approach overview
Problem Overview: You are given a numeric string num and an array change where each digit d can be replaced with change[d]. You may choose one contiguous substring and mutate its digits using this mapping. The goal is to produce the lexicographically largest possible number.
Approach 1: Greedy Mutation Window (O(n) time, O(1) space)
The optimal strategy is greedy. Scan the string from left to right and look for the first position where mutating the digit increases its value (change[d] > d). Once you start mutating, continue replacing digits while the mapped value is greater than or equal to the original digit. If the mapped digit becomes smaller, stop the mutation immediately because extending the substring would reduce the number. This works because earlier digits contribute more to the overall value of the number, so maximizing the leftmost improvable position yields the best result. The algorithm performs a single pass through the string and mutates digits in place.
This greedy observation avoids trying multiple substrings. Instead of exploring combinations, you simply expand the first profitable mutation segment and stop once the replacement no longer helps. Time complexity is O(n) since each digit is processed once, and space complexity is O(1) aside from the output string. The technique is a classic greedy decision pattern often seen in greedy optimization problems involving string manipulation.
Approach 2: Two-Pointer Expansion (O(n) time, O(1) space)
You can also view the problem as identifying a mutation window using two pointers. First pointer scans for the starting index where replacing a digit improves the value (change[d] > d). Once found, a second pointer expands the substring while replacements do not decrease the digit (change[d] >= d). During this expansion, replace digits directly in the result string. When the condition fails, stop the window and return the final number.
This approach expresses the same logic using explicit window boundaries. The left pointer marks the first beneficial mutation, and the right pointer grows the substring while the mapping remains non-decreasing. It’s useful if you want to reason about substring boundaries or implement the logic in languages where window-style iteration is clearer. Complexity remains O(n) time and O(1) extra space since each character is visited at most once.
Recommended for interviews: The greedy single-pass approach is what most interviewers expect. It shows that you understand how lexicographic maximization works and why starting mutation at the earliest beneficial index is optimal. Explaining the reasoning—start when change[d] > d, continue while change[d] >= d, stop when it becomes smaller—demonstrates strong problem-solving intuition with array-based digit mappings.
Approach 1: Greedy Approach
The key idea is to identify a starting point where mutating will increase the number and continue mutating while the mutation continues to increase the number. Once the mutation starts decreasing the number, stop mutating.
Using a greedy strategy helps in efficiently finding this optimal point where the mutated number is larger than the original.
def maximize_number(num: str, change: List[int]) -> str:
num_list = list(num)
started = False
for i in range(len(num_list)):
digit = int(num_list[i])
if change[digit] > digit:
num_list[i] = str(change[digit])
started = True
elif started and change[digit] < digit:
break
return ''.join(num_list)
# Example usage:
num = "132"
change = [9, 8, 5, 0, 3, 6, 4, 2, 6, 8]
print(maximize_number(num, change)) # Outputs: 832public class Main {
public static String maximizeNumber(String num, int[] change) {
StringBuilder sb = new StringBuilder(num);
boolean started = false;
for (int i = 0; i < sb.length(); i++) {
int digit = sb.charAt(i) - '0';
if (change[digit] > digit) {
sb.setCharAt(i, (char) ('0' + change[digit]));
started = true;
} else if (started && change[digit] < digit) {
break;
}
}
return sb.toString();
}
public static void main(String[] args) {
String num = "132";
int[] change = {9, 8, 5, 0, 3, 6, 4, 2, 6, 8};
System.out.println(maximizeNumber(num, change)); // Outputs: 832
}
}#include <iostream>
#include <string>
#include <vector>
std::string maximizeNumber(std::string num, std::vector<int>& change) {
bool started = false;
for (char& c : num) {
int digit = c - '0';
if (change[digit] > digit) {
c = '0' + change[digit];
started = true;
} else if (started && change[digit] < digit) {
break;
}
}
return num;
}
int main() {
std::string num = "132";
std::vector<int> change = {9, 8, 5, 0, 3, 6, 4, 2, 6, 8};
std::cout << maximizeNumber(num, change) << std::endl; // Outputs: 832
return 0;
}function maximizeNumber(num, change) {
let numArray = num.split('');
let started = false;
for (let i = 0; i < numArray.length; i++) {
let digit = parseInt(numArray[i], 10);
if (change[digit] > digit) {
numArray[i] = change[digit].toString();
started = true;
} else if (started && change[digit] < digit) {
break;
}
}
return numArray.join('');
}
// Example usage:
const num = "132";
const change = [9, 8, 5, 0, 3, 6, 4, 2, 6, 8];
console.log(maximizeNumber(num, change)); // Outputs: 832#include <stdio.h>
#include <string.h>
char* maximizeNumber(char* num, int* change) {
int n = strlen(num);
int started = 0;
for (int i = 0; i < n; ++i) {
int digit = num[i] - '0';
if (change[digit] > digit) {
num[i] = change[digit] + '0';
started = 1;
} else if (change[digit] < digit && started) {
break;
}
}
return num;
}
int main() {
char num[] = "132";
int change[] = {9, 8, 5, 0, 3, 6, 4, 2, 6, 8};
printf("%s\n", maximizeNumber(num, change)); // Outputs: 832
return 0;
}using System;
public class Solution {
public string MaximizeNumber(string num, int[] change) {
char[] numArray = num.ToCharArray();
bool started = false;
for (int i = 0; i < numArray.Length; i++) {
int digit = numArray[i] - '0';
if (change[digit] > digit) {
numArray[i] = (char) ('0' + change[digit]);
started = true;
} else if (started && change[digit] < digit) {
break;
}
}
return new string(numArray);
}
public static void Main() {
string num = "132";
int[] change = {9, 8, 5, 0, 3, 6, 4, 2, 6, 8};
Console.WriteLine(new Solution().MaximizeNumber(num, change)); // Outputs: 832
}
}In Python, this solution converts the string to a list to modify individual characters easily. It then looks for opportunities to replace each digit with a larger digit, as specified by the change array. When the mutation no longer increases the number, the loop ends to retain the largest possible number.
Time Complexity: O(n), where n is the length of the input string num.
Space Complexity: O(n), due to the list being created to hold the characters of num.
Approach 2: Two-Pointer Approach
This approach involves using two pointers to carefully choose the optimal substring to mutate. By determining the longest sequence from a potential starting point where mutation increases the number, this method extends the efficiency of the previous method for better clarity and handling.
def maximize_number(num: str, change: List[int]) -> str:
num_list = list(num)
i = 0
while i < len(num_list) and change[int(num_list[i])] <= int(num_list[i]):
i += 1
while i < len(num_list) and change[int(num_list[i])] >= int(num_list[i]):
num_list[i] = str(change[int(num_list[i])])
i += 1
return ''.join(num_list)
# Example usage:
num = "021"
change = [9, 4, 3, 5, 7, 2, 1, 9, 0, 6]
print(maximize_number(num, change)) # Outputs: 934public class Main {
public static String maximizeNumber(String num, int[] change) {
char[] numArray = num.toCharArray();
int i = 0;
while (i < numArray.length && change[numArray[i] - '0'] <= numArray[i] - '0') {
i++;
}
while (i < numArray.length && change[numArray[i] - '0'] >= numArray[i] - '0') {
numArray[i] = (char) ('0' + change[numArray[i] - '0']);
i++;
}
return new String(numArray);
}
public static void main(String[] args) {
String num = "021";
int[] change = {9, 4, 3, 5, 7, 2, 1, 9, 0, 6};
System.out.println(maximizeNumber(num, change)); // Outputs: 934
}
}#include <iostream>
#include <string>
#include <vector>
std::string maximizeNumber(std::string num, std::vector<int>& change) {
int i = 0;
while (i < num.size() && change[num[i] - '0'] <= num[i] - '0') {
i++;
}
while (i < num.size() && change[num[i] - '0'] >= num[i] - '0') {
num[i] = change[num[i] - '0'] + '0';
i++;
}
return num;
}
int main() {
std::string num = "021";
std::vector<int> change = {9, 4, 3, 5, 7, 2, 1, 9, 0, 6};
std::cout << maximizeNumber(num, change) << std::endl; // Outputs: 934
return 0;
}function maximizeNumber(num, change) {
let numArray = num.split('');
let i = 0;
while (i < numArray.length && change[parseInt(numArray[i], 10)] <= parseInt(numArray[i], 10)) {
i++;
}
while (i < numArray.length && change[parseInt(numArray[i], 10)] >= parseInt(numArray[i], 10)) {
numArray[i] = change[parseInt(numArray[i], 10)].toString();
i++;
}
return numArray.join('');
}
// Example usage:
const num = "021";
const change = [9, 4, 3, 5, 7, 2, 1, 9, 0, 6];
console.log(maximizeNumber(num, change)); // Outputs: 934#include <stdio.h>
#include <string.h>
char* maximizeNumber(char* num, int* change) {
int n = strlen(num);
int i = 0;
while (i < n && change[num[i] - '0'] <= num[i] - '0') {
i++;
}
for (; i < n && change[num[i] - '0'] >= num[i] - '0'; ++i) {
num[i] = change[num[i] - '0'] + '0';
}
return num;
}
int main() {
char num[] = "021";
int change[] = {9, 4, 3, 5, 7, 2, 1, 9, 0, 6};
printf("%s\n", maximizeNumber(num, change)); // Outputs: 934
return 0;
}using System;
public class Solution {
public string MaximizeNumber(string num, int[] change) {
char[] numArray = num.ToCharArray();
int i = 0;
while (i < numArray.Length && change[numArray[i] - '0'] <= numArray[i] - '0') {
i++;
}
while (i < numArray.Length && change[numArray[i] - '0'] >= numArray[i] - '0') {
numArray[i] = (char)('0' + change[numArray[i] - '0']);
i++;
}
return new string(numArray);
}
public static void Main() {
string num = "021";
int[] change = {9, 4, 3, 5, 7, 2, 1, 9, 0, 6};
Console.WriteLine(new Solution().MaximizeNumber(num, change)); // Outputs: 934
}
}The Python solution functions by using a two-step sequence to firstly identify the optimal starting point for transformation, followed by mutating the string while it leads to a larger number.
Time Complexity: O(n).
Space Complexity: O(n) due to list creation.
Approach 3: Greedy
According to the problem description, we can start from the highest digit of the string and greedily perform continuous replacement operations until we encounter a digit smaller than the current digit.
First, we convert the string num into a character array s and use a variable changed to record whether a change has already occurred, initially changed = false.
Then we traverse the character array s. For each character c, we convert it to a number d = change[int(c)]. If a change has already occurred and d < c, it means we cannot continue changing, so we exit the loop immediately. Otherwise, if d > c, it means we can replace c with d. At this point, we set changed = true and replace s[i] with d.
Finally, we convert the character array s back to a string and return it.
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the string num.
function maximumNumber(num: string, change: number[]): string {
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('');
}func maximumNumber(num string, change []int) string {
s := []byte(num)
changed := false
for i, c := range num {
d := byte('0' + change[c-'0'])
if changed && d < s[i] {
break
}
if d > s[i] {
s[i] = d
changed = true
}
}
return string(s)
}impl Solution {
pub fn maximum_number(num: String, change: Vec<i32>) -> String {
let mut s: Vec<char> = num.chars().collect();
let mut changed = false;
for i in 0..s.len() {
let d = (change[s[i] as usize - '0' as usize] + '0' as i32) as u8 as char;
if changed && d < s[i] {
break;
}
if d > s[i] {
changed = true;
s[i] = d;
}
}
s.into_iter().collect()
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Greedy Approach | Time Complexity: O(n), where n is the length of the input string |
| Two-Pointer Approach | Time Complexity: O(n). |
| Greedy | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy Mutation Window | O(n) | O(1) | Best general solution. Single pass, minimal logic, commonly expected in interviews. |
| Two-Pointer Expansion | O(n) | O(1) | Useful when reasoning about substring boundaries or implementing window-based logic. |
Frequently asked questions
Is Largest Number After Mutating Substring easy or hard?
The problem is rated Medium because the implementation is simple but the greedy insight is not immediately obvious. Many candidates initially try brute force over all substrings, which would be inefficient. Recognizing that only the first beneficial mutation window matters leads to the optimal linear solution.
How to solve Largest Number After Mutating Substring in O(n)?
Iterate through the string and find the first digit where change[d] > d. Start mutating from that position and replace digits while change[d] >= d. Stop when the mapped digit becomes smaller than the original. This greedy expansion ensures the earliest possible improvement, which maximizes the overall number.
What is the best approach for Largest Number After Mutating Substring?
The greedy approach is the most efficient and widely expected solution. Scan the string from left to right and start mutating when the mapped digit becomes larger than the original. Continue while the mapped value is greater than or equal to the current digit. This produces the lexicographically largest number in O(n) time.
What data structure is used in Largest Number After Mutating Substring?
The main data structures are a string for the number and an integer array of size 10 representing digit mappings. The algorithm performs direct index lookups in the mapping array while scanning the string. No additional complex structures such as heaps or hash maps are required.
What is the time complexity of Largest Number After Mutating Substring?
The optimal solution runs in O(n) time where n is the length of the string. Each digit is visited once during the left‑to‑right scan. Space complexity is O(1) because the mutation happens directly in the result string without extra data structures.
Largest Number After Mutating Substring Python or Java solution approach?
Both Python and Java implementations follow the same greedy logic. Convert the string to a mutable array or string builder, scan until change[d] > d, mutate digits while change[d] >= d, and stop once the condition fails. The algorithm remains O(n) time and O(1) extra space.
Is Largest Number After Mutating Substring asked at Google, Amazon, or Meta?
Problems involving greedy digit transformations and substring decisions are common in interviews at companies like Google, Amazon, and Meta. This problem tests the ability to recognize greedy optimization and lexicographic ordering in strings, which frequently appears in coding interviews.