Abstract / Summary

Given a target string and a robot that can only print characters in order from a fixed list, output the lexicographically smallest string the robot can print to match the target.

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 62% (100k+ submissions).

Typical patterns to solve this problem:

• Greedy
• Hash Table
• 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 solves the “robot with string” problem by simulating a stack-based robot that can either push the next character of the input string onto a temporary buffer or pop the top of that buffer into the final output. The algorithm builds the lexicographically smallest possible result while preserving the order constraints imposed by the robot’s operations. It does so in a single pass over the input, maintaining a count of remaining characters to decide when a buffered character can safely be emitted.

Key Steps

Counting Remaining Characters

wait = defaultdict(int)
for c in s:
    wait[c] += 1
wait["zz"] = 1  # stop marker

A dictionary named wait records how many times each character still appears later in the input. The extra entry "zz" with a count of 1 acts as a sentinel that guarantees min(wait) is always defined, preventing a runtime error when the buffer becomes empty.

Pushing Characters onto the Buffer

t.append(c)
wait[c] -= 1
if wait[c] == 0:
    del wait[c]

For each character c in the source string, the algorithm pushes c onto the list t, which functions as a stack. The count for c in wait is decremented, and the entry is removed when no further occurrences remain. This removal keeps the dictionary minimal, ensuring that the subsequent minimum lookup only considers characters that are still pending.

Emitting Characters from the Buffer

while t and t[-1] <= min(wait):
    result += t.pop()

After each push, the algorithm checks whether the top of the stack t[-1] is not greater than the smallest character that still appears later (min(wait)). If this condition holds, the top character can be safely moved to the output result. The loop repeats until the condition fails, guaranteeing that no smaller character is left undispatched behind a larger one.

Edge Cases Handled

When the input string is empty, the initial loop that populates wait does not execute, but the sentinel entry "zz" remains, so min(wait) yields "zz". The subsequent processing loop never runs, and the function returns an empty string, correctly handling the empty-input edge case.

If the input consists of a single repeated character, such as "aaaa", the wait dictionary initially holds {'a': 4, 'zz': 1}. As each 'a' is pushed, its count drops to zero and the entry is removed, leaving only the sentinel. The condition t[-1] <= min(wait) becomes true after each push, causing each 'a' to be immediately popped to the result. The output matches the input, demonstrating correct handling of uniform strings.

When the smallest remaining character appears later in the string, the algorithm retains larger characters on the stack until the smaller one is encountered. For example, with input "cbacd", the buffer will hold 'c' and 'b' while 'a' is still pending, preventing premature emission of 'c' and 'b'. Once 'a' is processed, the condition allows 'b' and then 'c' to be emitted in proper order.

Performance Optimizations

The use of a defaultdict(int) for wait provides O(1) amortized updates for character counts, avoiding the overhead of explicit existence checks. Deleting entries whose count reaches zero keeps the dictionary size proportional to the set of distinct characters that are still pending, which limits the cost of the min(wait) operation. Because min(wait) only scans the keys that remain, the algorithm benefits from the fact that the number of distinct characters in typical inputs (e.g., lowercase English letters) is bounded by a small constant, making the minimum lookup effectively constant time.

The stack t is implemented as a Python list, allowing both append and pop operations to run in O(1) time. By performing the emission loop immediately after each push, the algorithm avoids a separate traversal of the stack after the main pass, thereby achieving a single-pass solution without additional passes or auxiliary data structures.

The sentinel entry "zz" eliminates the need for an explicit empty-check before calling min(wait). This small trick removes a conditional branch inside the inner loop, contributing to a tighter execution path.

Overall, the combination of count-based lookahead, immediate emission, and careful dictionary management yields an efficient solution that processes each character a constant number of times while keeping auxiliary structures minimal.

Imagine a little robot standing in front of a conveyor belt that is carrying a jumble of alphabet blocks. This robot has a special task to organize these letters into a perfect line, but it has to follow a strict set of rules to make sure they come out in the most tidy order possible.

First, the robot looks at all the blocks coming down the belt and makes a secret list to remember how many of each letter are still heading its way. It keeps this list close by so it never forgets what is left to arrive.

As each block passes by, the robot puts it into a temporary pile, sort of like putting toys into a bin for safekeeping. Every time a block is placed into that bin, the robot marks it off its secret list. This helps the robot know which letters are still waiting to appear on the belt later.

The robot stays very alert and watches the smallest letter that is still left to come. If the toy in the robot's bin is just as small as or even smaller than any of the letters still waiting on the belt, the robot quickly picks it up and adds it to the final line. It keeps doing this over and over, checking its bin and comparing it to what is left, until every single block has been moved into the perfect line order. It is just like playing a careful game of sorting blocks to see them all lined up neatly at the very end.

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

not analyzed yet

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