Formatted question description: https://leetcode.ca/all/1946.html

1946. Largest Number After Mutating Substring

Level

Medium

Description

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

Solution

Use a greedy approach. Find the leftmost digit in num such that mutating the digit will increase num, and find the rightmost digit in num such that mutating the digit will decrease num. If such a leftmost digit does not exist, return num without mutating. If such a rightmost digit does not exist, then mutate all digits from the determined leftmost digit to the end of num. Finally, return the mutated num.

class Solution {
    public String maximumNumber(String num, int[] change) {
        char[] array = num.toCharArray();
        int length = array.length;
        int start = -1, end = length;
        for (int i = 0; i < length; i++) {
            int digit = array[i] - '0';
            if (digit < change[digit]) {
                start = i;
                break;
            }
        }
        if (start < 0)
            return num;
        for (int i = start + 1; i < length; i++) {
            int digit = array[i] - '0';
            if (digit > change[digit]) {
                end = i;
                break;
            }
        }
        for (int i = start; i < end; i++) {
            int digit = array[i] - '0';
            char changed = (char) ('0' + change[digit]);
            array[i] = changed;
        }
        return new String(array);
    }
}

All Problems

All Solutions