What is the main approach to solving the Largest Number After Mutating Substring problem?

The main approach is to use a greedy algorithm where you apply the mutation to a substring that maximizes the result while avoiding any mutations that result in smaller digits.

Why is it important to stop mutating when a digit becomes smaller?

Stopping prevents making changes that decrease the number's value, ensuring you only make mutations that improve or maintain the result.

How do you know where to stop mutating in the number?

You should stop mutating once you encounter a digit where its mapped value is smaller than the original. Further mutations would only decrease the number.

What happens if the number is already the largest possible without mutations?

If the number is already the largest possible, no mutation is applied, and the original number is returned as the result.

Can I mutate multiple substrings in this problem?

The problem restricts you to mutating only one substring of the number to achieve the largest possible result.

#1946

Medium

auto_awesome贪心·invariant

LeetCode 题解工作台

子字符串突变后可能得到的最大整数

给你一个字符串 num ，该字符串表示一个大整数。另给你一个长度为 10 且下标从 0 开始的整数数组 change ，该数组将 0-9 中的每个数字映射到另一个数字。更规范的说法是，数字 d 映射为数字 change[d] 。你可以选择突变 num 的任一子字符串。突变子字符串意味着将…

数组字符串贪心

题目描述

给你一个字符串 num ，该字符串表示一个大整数。另给你一个长度为 10 且 下标从 0 开始 的整数数组 change ，该数组将 0-9 中的每个数字映射到另一个数字。更规范的说法是，数字 d 映射为数字 change[d] 。

你可以选择突变 num 的任一子字符串。突变子字符串意味着将每位数字 num[i] 替换为该数字在 change 中的映射（也就是说，将 num[i] 替换为 change[num[i]]）。

请你找出在对 num 的任一子字符串执行突变操作（也可以不执行）后，可能得到的 最大整数 ，并用字符串表示返回。

子字符串 是字符串中的一个连续序列。

示例 1：

输入：num = "132", change = [9,8,5,0,3,6,4,2,6,8]
输出："832"
解释：替换子字符串 "1"：
- 1 映射为 change[1] = 8 。
因此 "132" 变为 "832" 。
"832" 是可以构造的最大整数，所以返回它的字符串表示。

示例 2：

输入：num = "021", change = [9,4,3,5,7,2,1,9,0,6]
输出："934"
解释：替换子字符串 "021"：
- 0 映射为 change[0] = 9 。
- 2 映射为 change[2] = 3 。
- 1 映射为 change[1] = 4 。
因此，"021" 变为 "934" 。
"934" 是可以构造的最大整数，所以返回它的字符串表示。

示例 3：

输入：num = "5", change = [1,4,7,5,3,2,5,6,9,4]
输出："5"
解释："5" 已经是可以构造的最大整数，所以返回它的字符串表示。

提示：

1 <= num.length <= 10⁵
num 仅由数字 0-9 组成
change.length == 10
0 <= change[d] <= 9

lightbulb

解题思路

方法一：贪心

根据题目描述，我们可以从字符串的高位开始，贪心的进行连续的替换操作，直到遇到一个比当前位数字小的数字为止。

我们先将字符串 $\textit{num}$ 转换为字符数组 $\textit{s}$ ，用一个变量 $\textit{changed}$ 记录是否已经发生过变化，初始时 $\textit{changed} = \text{false}$ 。

然后我们遍历字符数组 $\textit{s}$ ，对于每个字符 $\textit{c}$ ，我们将其转换为数字 $\textit{d} = \text{change}[\text{int}(\textit{c})]$ ，如果已经发生过变化且 $\textit{d} < \textit{c}$ ，则说明我们不能再继续变化，直接退出循环；否则，如果 $\textit{d} > \textit{c}$ ，则说明我们可以将 $\textit{c}$ 替换为 $\textit{d}$ ，此时我们将 $\textit{changed} = \text{true}$ ，并将 $\textit{s}[i]$ 替换为 $\textit{d}$ 。

最后我们将字符数组 $\textit{s}$ 转换为字符串并返回即可。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为字符串 $\textit{num}$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def maximumNumber(self, num: str, change: List[int]) -> str:
        s = list(num)
        changed = False
        for i, c in enumerate(s):
            d = str(change[int(c)])
            if changed and d < c:
                break
            if d > c:
                changed = True
                s[i] = d
        return "".join(s)

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Evaluating the candidate's ability to apply a greedy strategy in a non-trivial mutation problem.
question_mark
Checking for understanding of early stopping and its importance in optimizing the solution.
question_mark
Assessing the candidate's grasp of the pattern behind the greedy approach and its validation.

warning

常见陷阱

外企场景

error
Failing to stop mutating when the result becomes smaller than the original number.
error
Not recognizing that changing digits in the middle of the number can lead to smaller results if not carefully handled.
error
Mutating a digit even when it doesn’t improve the value, leading to unnecessary changes.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Allowing multiple substrings to mutate instead of just one.
arrow_right_alt
Different variations of the mapping where some digits map to the same value.
arrow_right_alt
Adding conditions like not allowing leading zeros after mutation.

help

常见问题

外企场景

继续练习

#2131 连接两字母单词得到的最长回文串 #1578 使绳子变成彩色的最短时间 #2573 找出对应 LCP 矩阵的字符串