Abstract / Summary

Given a string of digits remove some digits so the remaining digits are in increasing order and the resulting number is as small as possible

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 83% (300k+ submissions).

Typical patterns to solve this problem:

• Simulation
• Stack
• 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 provided implementation defines a method that removes characters from a string according to a simple rule: whenever a digit is encountered, the most recent non-digit character that has not yet been removed is deleted. The algorithm processes the input in a single left-to-right pass, maintains a mutable collection to represent the current state of the output, and finally assembles the remaining characters into the result string.

Core Logic

The method begins by allocating an empty list that will serve as a stack. This choice of data structure enables constant-time insertion and removal at the end of the collection, which is essential for the algorithm’s efficiency.

stack = []

The main loop iterates over each character in the input string. For each character the code distinguishes between digits and non-digits using the built-in str.isdigit() method.

for c in s:
    if c.isdigit():
        ...
    else:
        ...

When the character is a digit, the algorithm checks whether the stack currently holds any elements. If the stack is non-empty, the most recent character is removed with pop(). This conditional guard prevents an attempt to pop from an empty list, thereby handling cases where a digit appears before any removable character.

if c.isdigit():
    if stack:
        stack.pop()

If the character is not a digit, it is appended to the stack, preserving the order in which non-digit characters appear.

else:
    stack.append(c)

After the loop finishes, the characters that remain in the stack constitute the final string. The method joins the list into a single string using "".join(stack), which is more efficient than repeated string concatenation because it allocates the result only once.

return "".join(stack)

Edge-Case Handling

The algorithm gracefully manages several edge conditions without additional code.

When the input string is empty, the loop body never executes, the stack stays empty, and the join operation returns an empty string.

If the string consists solely of digits, each digit triggers the conditional pop, but because the stack is empty throughout, the inner if stack: guard prevents any removal operation, and the final result is again an empty string.

When a digit appears at the very beginning of the string, the same guard ensures that no pop is attempted, leaving the stack unchanged.

Consecutive digits are processed one after another; each digit attempts to delete the most recent character that survived previous deletions, effectively collapsing multiple backspace-like operations.

Digits interleaved with letters cause the most recent letter to be removed each time a digit is seen, which matches the intended “clear previous character” behavior even when the previous character itself was a digit that had already been ignored.

Performance Optimizations

The implementation leverages a list as a stack, which provides amortized O(1) time for both append and pop operations. This choice eliminates the need for costly shifting of elements that would occur with other mutable sequences.

The conditional if stack: before invoking pop() avoids unnecessary exception handling and ensures that the algorithm does not waste cycles on invalid operations.

By deferring the construction of the output string until after all characters have been processed, the code avoids repeated allocation that would arise from concatenating strings inside the loop. The final join call creates the result in a single pass over the accumulated characters, which is the most efficient way to build a string from a list in Python.

Overall, the method achieves linear processing of the input with minimal overhead, making it well-suited for strings of substantial length.

Imagine a little robot that has a tray for holding toy blocks. Every block has either a letter written on it or a number. The tray starts out completely empty. The robot looks at a long line of blocks one by one from left to right.

When the robot finds a block with a letter, it places that letter on the tray. It holds onto all the letters it finds.

When the robot finds a block with a number on it, that is like a special signal to remove the very last letter block that was put onto the tray. The robot picks up that last letter and takes it away as if it never existed. If the tray is already empty, the number does not do anything at all.

After the robot finishes looking at every block in the line, it just holds onto whatever letters are still sitting on the tray. These remaining letters are pushed together to make a new, shorter line.

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	Java	Python			C++		TS
	WalkCCC	Java	Python			C++
	leetcode.ca	Java	Python			C++	Go	TS
	Progiez	Java	Python			C++
github	charles-wangkai	Java
	fsq		Python
	JoshCrozier			JS
	Shamik07				Dart
	varunu28	Java
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
Progiez	C++, Java, Python
charles-wangkai	Java
fsq	Python
JoshCrozier	JavaScript
Shamik07	Dart
varunu28	Java

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