Largest Number After Mutating Substring

Medium
1407.

Largest Number After Mutating Substring

Largest Number After Mutating Substring is a medium coding problem on arrays, strings and greedy, asked in Amazon and Google interviews.

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^5
  • num consists of digits only
  • change.length == 10
  • 0 <= change[d] <= 9
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} num
 * @param {number[]} change
 * @return {string}
 */
var maximumNumber = function(num, change) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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^5
  • num consists of digits only
  • change.length == 10
  • 0 <= change[d] <= 9

Hints for Largest Number After Mutating Substring

  1. Hint 1

    All results have the same length, so the leftmost digit you can raise matters more than everything after it.

  2. Hint 2

    Start the substring at the first digit d with change[d] > d.

  3. Hint 3

    Then keep extending while change[d] >= d and 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

  1. Scan for the first index i whose digit d has change[d] > d. If there is none, return num unchanged.
  2. From i, replace each digit d by change[d] while change[d] >= d.
  3. 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] == d must 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 num when 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.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Strings