LeetCode 1946 - Largest Number After Mutating Substring

LeetCode Problem 1946

Difficulty: 🟡 Medium
Topics: Array, String, Greedy

Solution

Problem Understanding

This problem asks us to construct the lexicographically largest possible numeric string after optionally applying a single transformation operation on one contiguous substring of the input string num. Each digit in num can be transformed independently using a fixed mapping array change, where change[d] defines the replacement digit for digit d.

We are allowed to choose at most one substring and apply the transformation to every digit inside that substring exactly once. Digits outside the chosen substring remain unchanged. The goal is to choose both the substring boundaries and whether to apply the operation at all such that the resulting string represents the largest possible integer in lexicographical order.

The input constraints indicate that num can be up to length 100,000, which strongly suggests that any quadratic or worse solution will not be feasible. The change array has fixed size 10, meaning digit transformations are constant-time lookups.

Several edge cases are important. If no digit transformation improves the number, the correct answer is the original string. If multiple substrings could improve the result, we must ensure that we choose the one that maximizes the final value under the constraint that only one contiguous segment can be mutated. Another subtle case occurs when transformations initially increase digit value but later decrease it, which defines the boundary of the valid substring.

Approaches

The brute-force approach considers every possible substring of num. For each substring, we simulate applying the digit transformation and construct a new string. We then compare all results and choose the maximum lexicographically. This works because it exhaustively checks all valid operations, ensuring correctness. However, it is far too slow because there are O(n^2) substrings, and each transformation costs O(n), leading to O(n^3) in a naive implementation or at best O(n^2), both of which are too large for n = 100,000.

The key insight is that we do not need to try all substrings. Instead, we observe that once we decide to start mutating at a position, we should continue mutating as long as the transformation does not reduce the digit value. The moment the transformation becomes worse than the original digit, we must stop, because extending further would only make the number smaller, and we are allowed only one contiguous segment.

Thus, the optimal solution is greedy: we find the first position where applying change improves the digit, start mutation there, and continue while it remains non-decreasing. This ensures maximal lexicographical gain.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n³)	O(n)	Try all substrings and simulate transformations
Optimal Greedy	O(n)	O(n)	Single pass to find best valid mutation window

Algorithm Walkthrough

The optimal algorithm is based on scanning the string once and carefully deciding where the mutation segment starts and ends.

1. Convert the string num into a list of characters so we can modify it efficiently. This avoids repeated string concatenation, which would be costly in Python.
2. Initialize a boolean flag started to track whether we have begun applying the mutation. Initially, we have not started because we have not found a beneficial starting point.
3. Iterate through each index i of the string from left to right. At each position, compare the original digit num[i] with its transformed value change[num[i]].
4. If we have not started a mutation and the transformed digit is greater than the original digit, we begin the mutation at this index. From this point onward, we apply the transformation to every digit until we decide to stop.
5. Once mutation has started, we continue applying it as long as change[num[i]] is greater than or equal to num[i]. This ensures we do not reduce the value of the number.
6. If we encounter a digit where change[num[i]] is strictly less than num[i], we stop the mutation immediately. From this point forward, all remaining digits stay unchanged, because only one contiguous substring is allowed.
7. After processing the entire string, convert the list of characters back into a string and return it.

Why it works: The algorithm enforces a single contiguous segment that is maximally beneficial. The greedy choice ensures we start as early as possible for maximum lexicographical gain, and we stop exactly when continuation would harm the result. This creates an optimal window that cannot be improved by shifting boundaries.

Python Solution

from typing import List

class Solution:
    def maximumNumber(self, num: str, change: List[int]) -> str:
        digits = list(num)
        started = False

        for i in range(len(digits)):
            d = ord(digits[i]) - ord('0')
            transformed = change[d]

            if not started:
                if transformed > d:
                    started = True
                    digits[i] = str(transformed)
            else:
                if transformed >= d:
                    digits[i] = str(transformed)
                else:
                    break

        return "".join(digits)

The implementation directly follows the greedy strategy. We iterate once over the string, decide when to start mutation, and apply transformation while it remains non-decreasing. The started flag ensures we maintain a single contiguous segment constraint.

Go Solution

func maximumNumber(num string, change []int) string {
	runes := []byte(num)
	started := false

	for i := 0; i < len(runes); i++ {
		d := int(runes[i] - '0')
		transformed := change[d]

		if !started {
			if transformed > d {
				started = true
				runes[i] = byte(transformed + '0')
			}
		} else {
			if transformed >= d {
				runes[i] = byte(transformed + '0')
			} else {
				break
			}
		}
	}

	return string(runes)
}

In Go, we use a byte slice instead of a string because strings are immutable. Converting to a byte slice allows in-place modification. The logic mirrors the Python solution exactly, with explicit integer-to-byte conversion for digit handling.

Worked Examples

Example 1

Input: num = "132", change = [9,8,5,0,3,6,4,2,6,8]

We process step by step:

At index 0, digit is 1, transformed is 8. Since 8 > 1, we start mutation here.

At index 0:

i	digit	change[d]	action
0	1	8	start, replace with 8

At index 1:

i	digit	change[d]	action
1	3	0	stop because 0 < 3

Final string becomes "832".

Example 2

Input: num = "021", change = [9,4,3,5,7,2,1,9,0,6]

At index 0, digit 0 maps to 9, which is beneficial, so we start immediately.

At index 0:

i	digit	change[d]	action
0	0	9	start, replace

At index 1:

i	digit	change[d]	action
1	2	3	continue

At index 2:

i	digit	change[d]	action
2	1	4	continue

Final result is "934".

Example 3

Input: num = "5", change = [1,4,7,5,3,2,5,6,9,4]

At index 0, digit 5 maps to 2, which is worse. We never start mutation.

Result remains "5".

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Single pass through the string with constant-time digit mapping
Space	O(n)	Output is stored in a mutable character array

The time complexity is linear because each character is visited at most once, and each operation inside the loop is O(1). Space complexity is linear due to conversion into a mutable structure for in-place updates.

Test Cases

assert Solution().maximumNumber("132", [9,8,5,0,3,6,4,2,6,8]) == "832"  # basic improvement case
assert Solution().maximumNumber("021", [9,4,3,5,7,2,1,9,0,6]) == "934"  # full substring mutation
assert Solution().maximumNumber("5", [1,4,7,5,3,2,5,6,9,4]) == "5"      # no beneficial change
assert Solution().maximumNumber("10", [0,1,2,3,4,5,6,7,8,9]) == "20"     # single digit start only
assert Solution().maximumNumber("333", [3,3,3,3,3,3,3,3,3,3]) == "333"   # all equal mapping
assert Solution().maximumNumber("13", [1,2,3,4,5,6,7,8,9,0]) == "23"     # partial improvement
assert Solution().maximumNumber("987654", [9,9,9,9,9,9,9,9,9,9]) == "987654"  # no change improves

Test	Why
"132" case	verifies standard greedy start/stop behavior
"021" case	verifies full substring mutation
"5" case	verifies no mutation case
"10" case	tests boundary where only first digit triggers
"333" case	tests equality handling
"13" case	tests partial improvement window
"987654" case	tests no-op when mapping is non-improving

Edge Cases

One important edge case is when no digit in the string can be improved by its mapping. In this case, the algorithm must never start the mutation window, and the original string must be returned unchanged. The started flag ensures this because it is only set when a strict improvement is found.

Another edge case occurs when the improvement starts at the first character and continues through the entire string. This happens when change[d] >= d for all digits after the first beneficial start. The algorithm handles this naturally by never encountering a break condition.

A third edge case involves early improvement followed by a sudden decrease in mapped value. This is critical because it defines the correct stopping boundary. The algorithm explicitly breaks at the first position where change[d] < d after mutation has started, ensuring that we do not violate the single-substring constraint or reduce the lexicographical value of the result.