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 thelargest possible integer after mutating (or choosing not to) a single substring of _num.

A substring is a contiguous sequence of characters within the string.

Examples

Example 1

1
2
3
4
5
6

Input: num = "_1_ 32", change = [9,8,5,0,3,6,4,2,6,8]
Output: "_8_ 32"
Explanation: Replace the substring "1":
- 1 maps to change[1] = 8.
Thus, "_1_ 32" becomes "_8_ 32".
"832" is the largest number that can be created, so return it.

Example 2

1
2
3
4
5
6
7
8

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

1
2
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

Method 1 – Greedy One-Pass Mutation

Intuition

To maximize the number, start mutating at the first position where the mapped digit is greater than the original, and keep mutating as long as the mapped digit is at least as large as the original. Stop at the first position where the mapped digit is less than the original.

Approach

  1. Convert num to a list of digits.
  2. Iterate through each digit:
    • If not mutating and mapped digit > original, start mutating.
    • If mutating and mapped digit < original, stop mutating.
    • If mutating, replace digit with mapped digit.
  3. Join the digits and return the result.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
public:
    string maximumNumber(string num, vector<int>& change) {
        string ans = num;
        bool mut = false;
        for (int i = 0; i < num.size(); ++i) {
            int d = num[i] - '0', c = change[d];
            if (!mut && c > d) { ans[i] = c + '0'; mut = true; }
            else if (mut && c >= d) ans[i] = c + '0';
            else if (mut && c < d) break;
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

func maximumNumber(num string, change []int) string {
    ans := []byte(num)
    mut := false
    for i := 0; i < len(num); i++ {
        d := int(num[i] - '0')
        c := change[d]
        if !mut && c > d {
            ans[i] = byte(c + '0')
            mut = true
        } else if mut && c >= d {
            ans[i] = byte(c + '0')
        } else if mut && c < d {
            break
        }
    }
    return string(ans)
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    public String maximumNumber(String num, int[] change) {
        char[] ans = num.toCharArray();
        boolean mut = false;
        for (int i = 0; i < num.length(); ++i) {
            int d = num.charAt(i) - '0', c = change[d];
            if (!mut && c > d) { ans[i] = (char)(c + '0'); mut = true; }
            else if (mut && c >= d) ans[i] = (char)(c + '0');
            else if (mut && c < d) break;
        }
        return new String(ans);
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    fun maximumNumber(num: String, change: IntArray): String {
        val ans = num.toCharArray()
        var mut = false
        for (i in num.indices) {
            val d = num[i] - '0'
            val c = change[d]
            if (!mut && c > d) { ans[i] = (c + '0').toChar(); mut = true }
            else if (mut && c >= d) ans[i] = (c + '0').toChar()
            else if (mut && c < d) break
        }
        return String(ans)
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution:
    def maximumNumber(self, num: str, change: list[int]) -> str:
        ans = list(num)
        mut = False
        for i, ch in enumerate(num):
            d = int(ch)
            c = change[d]
            if not mut and c > d:
                ans[i] = str(c)
                mut = True
            elif mut and c >= d:
                ans[i] = str(c)
            elif mut and c < d:
                break
        return ''.join(ans)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

impl Solution {
    pub fn maximum_number(num: String, change: Vec<i32>) -> String {
        let mut ans: Vec<u8> = num.bytes().collect();
        let mut mutating = false;
        for (i, &b) in num.as_bytes().iter().enumerate() {
            let d = (b - b'0') as usize;
            let c = change[d] as u8;
            if !mutating && c > b - b'0' {
                ans[i] = c + b'0';
                mutating = true;
            } else if mutating && c >= b - b'0' {
                ans[i] = c + b'0';
            } else if mutating && c < b - b'0' {
                break;
            }
        }
        String::from_utf8(ans).unwrap()
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    maximumNumber(num: string, change: number[]): string {
        const ans = num.split('')
        let mut = false
        for (let i = 0; i < num.length; ++i) {
            const d = +num[i], c = change[d]
            if (!mut && c > d) { ans[i] = String(c); mut = true }
            else if (mut && c >= d) ans[i] = String(c)
            else if (mut && c < d) break
        }
        return ans.join('')
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the length of num. Each digit is visited once.
  • 🧺 Space complexity: O(n), for the answer string.