1946. Largest Number After Mutating Substring LeetCode Solution
In this guide, you will get 1946. Largest Number After Mutating Substring LeetCode Solution with the best time and space complexity. The solution to Largest Number After Mutating Substring problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Largest Number After Mutating Substring
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.
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
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(n)
1946. Largest Number After Mutating Substring LeetCode Solution in C++
class Solution {
public:
string maximumNumber(string num, vector<int>& change) {
bool mutated = false;
for (char& c : num) {
const int d = c - '0';
c = '0' + max(d, change[d]);
if (mutated && d > change[d])
return num;
if (d < change[d])
mutated = true;
}
return num;
}
}; /* code provided by PROGIEZ */
1946. Largest Number After Mutating Substring LeetCode Solution in Java
class Solution {
public String maximumNumber(String num, int[] change) {
StringBuilder sb = new StringBuilder(num);
boolean mutated = false;
for (int i = 0; i < num.length(); ++i) {
final int d = num.charAt(i) - '0';
final char c = (char) ('0' + Math.max(d, change[d]));
sb.setCharAt(i, c);
if (mutated && d > change[d])
return sb.toString();
if (d < change[d])
mutated = true;
}
return sb.toString();
}
} // code provided by PROGIEZ
1946. Largest Number After Mutating Substring LeetCode Solution in Python
class Solution:
def maximumNumber(self, num: str, change: list[int]) -> str:
numList = list(num)
mutated = False
for i, c in enumerate(numList):
d = int(c)
numlist[i] = chr(ord('0') + max(d, change[d]))
if mutated and d > change[d]:
return ''.join(numList)
if d < change[d]:
mutated = True
return ''.join(numList) # code by PROGIEZ
