Abstract / Summary

Given a number as a string and digits to remove and append, find the largest possible number after one substring mutation.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 38% (70k+ submissions).

Typical patterns to solve this problem:

• Array
• Greedy
• String

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The maximumNumber method receives a numeric string num and a list change that maps each digit (0-9) to a replacement digit. The goal is to produce the lexicographically largest possible string by optionally replacing a contiguous segment of the original digits with their mapped values. The algorithm walks through the digits once, decides where a replacement segment should start, applies the best possible replacements, and stops as soon as the segment can no longer improve the result.

Key Steps

Convert the input string to a mutable integer list

size = len(num)
num  = [int(n) for n in num]

The original immutable string is transformed into a list of integers, allowing in-place updates while preserving the original order. The length is stored in size for potential future use.

Initialise control flags

again = True
replace = False

replace indicates whether the algorithm has entered a region where replacements are beneficial. again records whether a replacement has already been performed; it prevents further changes after the first improvement, ensuring the segment remains contiguous.

Iterate over each digit with its index

for i, n in enumerate(num):

The loop provides both the position i and the current digit n. This enables direct access to the corresponding entry in change and to modify the list at the same index.

Decide whether a replacement segment should start

if change[n] >= n:
    replace = True
elif replace and not again:
    break

If the mapped value is not smaller than the original digit, the algorithm marks the start of a possible replacement segment by setting replace to True. Once a replacement has been made (again becomes False), encountering a digit whose mapped value is smaller than the original triggers an early exit, because extending the segment would only reduce the result.

Apply the replacement while respecting the flags

if replace:
    if num[i] < change[n]:
        num[i] = change[n]
        again  = False

When inside a replacement region, the code checks whether the mapped digit is strictly larger than the current digit. If so, it overwrites the digit and flips again to False, signalling that the first improvement has occurred. Subsequent digits are only replaced if they continue to improve the number; otherwise the loop will break as described above.

Convert the modified list back to a string

return "".join(str(n) for n in num)

After processing, the integer list is transformed back into a concatenated string, which is the required output format.

Edge Cases Handled

When the mapped digit equals the original (change[n] == n), the algorithm treats it as a potential start of a replacement segment but does not modify the digit, preserving the original value while still allowing later improvements. If no digit can be increased because every change[n] is smaller than n, the replace flag never becomes True and the original string is returned unchanged. The early-break condition ensures that once a decreasing mapped value is encountered after a successful replacement, the algorithm stops, preventing a later increase that would break the contiguity rule. The code also correctly handles the situation where the entire string can be upgraded (all change[n] >= n), applying the maximum possible digit to each position without premature termination.

Performance Optimizations

The solution performs a single linear pass over the digits, avoiding any nested loops or repeated scans. Converting the input string to a list of integers up front enables constant-time element updates, eliminating the need for string slicing or concatenation during the iteration. The use of the again flag allows the loop to exit early as soon as the replacement segment can no longer improve the result, reducing unnecessary work on the trailing part of the string. Finally, the final conversion back to a string uses a generator expression inside join, which builds the result efficiently without creating intermediate lists.

Imagine a string of colorful wooden blocks sitting on the floor, each with a number painted on it. You have a special magic wand, and there is a secret list that tells you which numbers can trade places with bigger numbers to make the whole row as large as possible.

The code starts by looking at the line of blocks one by one, from the very first to the very last. It checks each block against the secret list to see if that number is smaller than or equal to what it could become.

When the code finds a block that can get bigger, it starts a transformation. It swaps the old number for the new, bigger one and keeps moving down the line to see if the next blocks can also grow. This continues as long as the numbers keep getting bigger or equal.

If the numbers are getting bigger and then suddenly hit a block that is too small to grow, the code stops the transformation. It knows that once the numbers have stopped growing after a good run, there is no use in trying to change any more blocks further down the row. Everything is then put back together into a long string of characters to show the brand new, bigger number.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: linear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++		Python	Java				TS
	WalkCCC	C++		Python	Java
	leetcode.ca	C++	JS	Python	Java		Go	Rust	TS
	Progiez	C++		Python	Java
github	black-shadows	C++
	charles-wangkai				Java
	everthis		JS
	fsq	C++
	haoel	C++
	JoshCrozier		JS
	lkwq007			Python
	suxrobGM					C#
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, JavaScript, Python, Rust, TypeScript
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fsq	C++
haoel	C++
JoshCrozier	JavaScript
lkwq007	Python
suxrobGM	C#

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality