1946. Largest Number After Mutating Substring


Problem Description

In this problem, you have a string num that represents a large integer and an array change of ten integers, where each index of the array corresponds to a digit from 0 to 9. The value at each index d in the array is the digit that d should be mapped to. You are allowed to mutate a single contiguous substring of num by replacing each digit in it according to the mapping defined by the change array. The goal is to perform this operation in such a way that the resulting integer, when converted back to a string, is as large as possible. To make it clearer, mutating a substring means selecting a continuous sequence of digits in num and replacing each of those digits with their corresponding digit from the change array. You can also choose not to mutate any substring at all. A substring here means any contiguous sequence of characters within the string num.

Intuition

To get the largest possible number after mutation, one should start mutating the earliest digit in num that can be increased by the corresponding digit in change. Once you start mutation, continue to mutate sequentially as long as the digits can be increased or stay the same after replacement. If at any point, a subsequent digit cannot be increased through mutation (i.e., the digit in num is greater than the mapping digit in change), then stop the mutation process because continuing would result in a smaller number.

The reasoning for starting at the earliest possible digit is to take advantage of the positional value in numbers: a digit towards the left has more value than a digit towards the right. Thus, to maximize the number, we want to increase the value of the leftmost possible digits. Moreover, at the first occurrence where mutating does not increase the number anymore, we should stop. This strategy ensures we get the highest value after a single substring mutation.

The given solution implements this approach by:

  1. Converting the string num into a list of characters s for easy manipulation.
  2. Iterating through this list and checking, at each index, if the digit can be increased via mutation.
  3. If a digit can be increased, mutating the current digit and continuing to the next digit until a digit is found that would not be increased by mutation, at which point the loop breaks.
  4. After the loop, the possibly mutated list of characters s is joined back together to form a string representing the largest possible integer after mutation.

Learn more about Greedy patterns.

Solution Approach

The algorithm uses a simple linear scan to implement the intuitive approach. Here's how the code executes the solution:

  1. First, the string num is converted into a list of characters s, which allows for indexed access and in-place modification of the individual digits.

  2. The algorithm then enters a loop, iterating over each digit in the list s. For each digit at index i, it is cast to an integer and compared against the digit it would map to in the change array.

  3. If the digit from the change array is greater than the current digit in s, this means we can "mutate" this digit to get a larger number. The while loop is then entered to continue mutation as long as the criterion is met (i.e., the digit at the current index is less than or equal to the corresponding digit in the change array):

    1while i < len(s) and int(s[i]) <= change[int(s[i])]:
    2    s[i] = str(change[int(s[i])])
    3    i += 1
  4. The mutation starts at the current index i and continues to the subsequent digits as long as they are less than or equal to their mapped counterparts in the change array. This ensures that the number is strictly increasing or staying the same as we continue the mutation.

  5. Once a digit is encountered where the change array does not provide a greater or equal digit, the while loop is exited (intuitively, mutation ends), and the outer for loop is also exited with a break statement. This ensures we are only mutating one contiguous substring.

  6. The list is joined back into a string with return ''.join(s), providing the mutated (or unmutated, if no mutation took place) number as the output.

In this approach, the data structure used is a list for s, which allows modifications to be made. No complex algorithms or data patterns are needed—just simple conditional logic and iteration.

String manipulation happens in place within the list of characters, which avoids the need for creating additional strings during the process. This is efficient in terms of space usage, since strings in Python are immutable and creating substrings or modifying strings would otherwise require additional space.

The linear scan enforces that the loop runs with a complexity of O(n), where n is the length of num. This makes the algorithm efficient because it scans each digit only once and performs in-place mutations without the overhead of additional string manipulation functions.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What's the output of running the following function using input 56?

1KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13    def dfs(path, res):
14        if len(path) == len(digits):
15            res.append(''.join(path))
16            return
17
18        next_number = digits[len(path)]
19        for letter in KEYBOARD[next_number]:
20            path.append(letter)
21            dfs(path, res)
22            path.pop()
23
24    res = []
25    dfs([], res)
26    return res
27
1private static final Map<Character, char[]> KEYBOARD = Map.of(
2    '2', "abc".toCharArray(),
3    '3', "def".toCharArray(),
4    '4', "ghi".toCharArray(),
5    '5', "jkl".toCharArray(),
6    '6', "mno".toCharArray(),
7    '7', "pqrs".toCharArray(),
8    '8', "tuv".toCharArray(),
9    '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13    List<String> res = new ArrayList<>();
14    dfs(new StringBuilder(), res, digits.toCharArray());
15    return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19    if (path.length() == digits.length) {
20        res.add(path.toString());
21        return;
22    }
23    char next_digit = digits[path.length()];
24    for (char letter : KEYBOARD.get(next_digit)) {
25        path.append(letter);
26        dfs(path, res, digits);
27        path.deleteCharAt(path.length() - 1);
28    }
29}
30
1const KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13    let res = [];
14    dfs(digits, [], res);
15    return res;
16}
17
18function dfs(digits, path, res) {
19    if (path.length === digits.length) {
20        res.push(path.join(''));
21        return;
22    }
23    let next_number = digits.charAt(path.length);
24    for (let letter of KEYBOARD[next_number]) {
25        path.push(letter);
26        dfs(digits, path, res);
27        path.pop();
28    }
29}
30

Example Walkthrough

Let's say we are given the string num = "132" and the change array change = [9, 8, 5, 0, 3, 2, 1, 2, 6, 4]. Here is a step-by-step explanation to illustrate how the solution approach would work on this example:

  1. Convert num to a list s of characters for manipulation:

    1s = ['1', '3', '2']
  2. Start iterating from left to right over each character in s.

  3. For the first digit in s, '1', the corresponding digit in the change array is change[1] = 8. Since 8 is greater than 1, we can mutate this digit:

    1s = ['8', '3', '2'] // The first digit is mutated to '8'
  4. Continue to the next digit, '3'. The corresponding digit in the change array is change[3] = 0. Since 0 is not greater than 3, we should stop mutating. However, we should check if the new digit is the same or greater to allow the mutation to continue, but in our case, it's not, so we stop.

  5. The algorithm would have ideally continued mutating if the change digits were greater than or equal to the current digits in s, but since the digit 3 would decrease if we mutate it using the change array, the mutation process ends.

  6. Finally, the list s is joined to form a string, giving us the result:

    1result = '832'

And that's the final answer. We obtain the largest possible number after mutating the string num with the given change array using only one continuous substring which, in this case, was just the first digit.

Solution Implementation

1class Solution:
2    def maximumNumber(self, num: str, digit_mappings: List[int]) -> str:
3        # Convert the number string to a list of characters for easy manipulation
4        num_list = list(num)
5      
6        # Traverse through the number's characters
7        for index, char in enumerate(num_list):
8            # Determine if the current digit can be increased using the provided mapping
9            if digit_mappings[int(char)] > int(char):
10                # If it can, change the current digit and continue changing subsequent digits
11                # until no further changes are beneficial
12                while index < len(num_list) and int(num_list[index]) <= digit_mappings[int(num_list[index])]:
13                    num_list[index] = str(digit_mappings[int(num_list[index])])
14                    index += 1
15                # Once a change is not beneficial, break the loop as no further checks are necessary
16                break
17      
18        # Join the characters back into a string and return the result
19        return ''.join(num_list)
20
1class Solution {
2    public String maximumNumber(String num, int[] change) {
3        // Convert the input string to a character array to manipulate individual numbers.
4        char[] digits = num.toCharArray();
5      
6        // Iterate through each digit in the character array.
7        for (int i = 0; i < digits.length; ++i) {
8            // Check if the current digit can be increased according to the change array.
9            if (change[digits[i] - '0'] > digits[i] - '0') {
10                // Continue to change the current and subsequent digits until it's no longer beneficial.
11                while (i < digits.length && digits[i] - '0' <= change[digits[i] - '0']) {
12                    // Apply the change to the current digit.
13                    digits[i] = (char) (change[digits[i] - '0'] + '0');
14                    i++;
15                }
16                // Once the changing is done, or no longer beneficial, exit the loop.
17                break;
18            }
19        }
20        // Return the new string with applied changes.
21        return new String(digits);
22    }
23}
24
1class Solution {
2public:
3    // This method returns the maximum number by swapping digits as per the change vector.
4    string maximumNumber(string num, const vector<int>& change) {
5        int numLength = num.size(); // Store the length of the input number string
6
7        // Iterate over each digit of the number string
8        for (int i = 0; i < numLength; ++i) {
9            int digit = num[i] - '0'; // Convert character to digit
10
11            // Check if the current digit can be increased by using the change array
12            if (change[digit] > digit) {
13                // Keep swapping until the change array offers a digit greater than or equal to the current digit
14                while (i < numLength && change[digit] >= digit) {
15                    num[i] = change[digit] + '0'; // Perform the swap by updating the character in the string
16                    ++i; // Move to the next digit
17
18                    // Make sure we are not at the end of the string and update the digit if not
19                    if(i < numLength) {
20                        digit = num[i] - '0';
21                    }
22                }
23                break; // Once we cannot swap anymore, exit the loop as the string is maximized
24            }
25        }
26        return num; // Return the modified number string which is now the maximum number
27    }
28};
29
1// This method returns the maximum number by swapping digits as per the change array.
2function maximumNumber(numStr: string, change: number[]): string {
3    let numLength = numStr.length; // Store the length of the input number string
4
5    // Convert the string to an array of characters for easy manipulation
6    let numArr = numStr.split('');
7
8    // Iterate over each digit of the number array
9    for (let i = 0; i < numLength; ++i) {
10        // Parse the current character to get the digit
11        let digit = parseInt(numArr[i], 10);
12
13        // Check if the current digit can be increased by using the change array
14        if (change[digit] > digit) {
15            // Keep swapping until the change array offers a digit greater than or equal to the current one
16            while (i < numLength && change[digit] >= digit) {
17                // Perform the swap by updating the character in the array
18                numArr[i] = change[digit].toString();
19                ++i; // Move to the next digit
20
21                if (i < numLength) {
22                    // Update the digit if we are not at the end of the array
23                    digit = parseInt(numArr[i], 10);
24                }
25            }
26            // Once we cannot swap anymore, break out of the loop as the string is now maximized
27            break;
28        }
29    }
30  
31    // Join the array of characters back into a string to get the modified number
32    return numArr.join('');
33}
34
35// Example usage:
36// const result = maximumNumber("132", [9, 8, 5, 0, 3, 4, 2, 1, 9, 8]);
37// console.log(result); // Output should be "832" after applying the change array.
38

Time and Space Complexity

Time Complexity

The time complexity of the given code is O(n), where n is the length of the string num. The code consists of a single loop that goes through the characters of the string once, starting from the beginning of the string. The inner while loop runs only when a digit can be changed to a higher digit based on the change array, and it runs at most n times in total, not n times for each character, since the loop breaks once no more changes can be done. Therefore, in the worst-case scenario, each character is evaluated once, and the change is applied within the same iteration without causing another full scan of the string.

Space Complexity

The space complexity is O(n), where n is the length of the input string num. This is due to the conversion of the input string num to a list s, which creates a separate array of characters of size n. Other than that, there are no significant data structures used that would increase the space complexity.

Learn more about how to find time and space complexity quickly using problem constraints.


Fast Track Your Learning with Our Quick Skills Quiz:

Which type of traversal does breadth first search do?


Recommended Readings


Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


🪄