Abstract / Summary

Remove stars by replacing them with the smallest possible letter to get the lexicographically smallest string.

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 51% (200k+ submissions).

Typical patterns to solve this problem:

• Greedy
• Hash Table
• Heap (Priority Queue)
• 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 class Solution with a method clearStars that processes a string containing lowercase letters and asterisks (*). Each asterisk triggers the removal of the most recent occurrence of the smallest character that appears earlier in the string. The algorithm maintains data structures to locate and delete the required characters efficiently, then constructs the final string without the asterisks and the deleted characters.

Core Logic

Initialization of Helper Structures

The method begins by creating three containers:

seen   = []          # min-heap of (character, negative position)
delete = set()       # indices of characters that must be removed

seen is a heap that stores pairs consisting of a character and the negative of its index. The negative index turns the heap into a max-heap with respect to position while preserving the min-heap ordering for characters. delete is a hash set that enables constant-time checks for indices that have been marked for removal.

Scanning the Input String

The algorithm iterates over the input string with enumerate, exposing both the index i and the character c:

for i, c in enumerate(s):
    if c == "*":
        # deletion logic
    else:
        heappush(seen, (c, -i))

When the current character is not an asterisk, the pair (c, -i) is pushed onto seen. This step records every ordinary character together with its position, preserving the order needed for later deletions.

Handling an Asterisk

When an asterisk is encountered, the algorithm extracts the element with the smallest character from seen. Because the heap stores negative positions, the extracted tuple also yields the most recent occurrence of that character:

_, pos = heappop(seen)
delete.add(-pos)

heappop removes the smallest character; pos is the negative index, so -pos recovers the original index. That index is added to delete, marking the character for exclusion from the final result.

Building the Result

After the scan completes, a list comprehension filters out asterisks and any character whose index appears in delete:

result = [c for i, c in enumerate(s) if c != "*" and i not in delete]
return "".join(result)

The comprehension iterates once more over the original string, preserving the original order of the remaining characters. The list of characters is then joined into a single string, which is returned as the output.

Edge Cases Addressed

The code naturally accommodates several boundary conditions:

• Empty Input - When s is an empty string, the loop body never executes, seen remains empty, and the final comprehension yields an empty list, resulting in an empty string return.
• No Asterisks - If the string contains only letters, the if c == "*" branch is never taken. All characters are pushed onto seen, but no deletions occur, so the final comprehension returns the original string unchanged.
• Consecutive Asterisks - Multiple asterisks in a row trigger successive heappop operations. Each pop removes the smallest character among those still present, respecting the “most recent occurrence” rule because the heap stores negative positions.
• Asterisk at the Beginning - The problem statement guarantees that an asterisk will never appear before any character to delete. In practice, if an asterisk were the first character, heappop would raise an exception due to an empty heap; however, the algorithm assumes valid input where this situation does not arise.
• All Characters Deleted - When every character is eventually removed by asterisks, delete ends up containing all indices. The final comprehension filters everything out, and the method returns an empty string.

Performance Optimizations

The implementation leverages several techniques to keep the processing efficient:

• Heap for Minimum Character Retrieval - By using a min-heap (seen), the algorithm obtains the smallest character in logarithmic time, avoiding a linear scan of the accumulated characters.
• Negative Index for Recent Position - Storing -i alongside each character allows the heap to prioritize the most recent occurrence when characters are equal, eliminating the need for a secondary data structure to track positions.
• Hash Set for Deletion Checks - The delete set provides O(1) membership testing during the final comprehension, ensuring that the filtering step does not degrade performance as the number of deletions grows.
• Single Pass Construction of Result - The final list comprehension iterates over the original string only once, building the output without additional intermediate structures or repeated lookups.

These choices collectively ensure that the method processes the input with a balanced trade-off between time spent maintaining ordering information and the speed of removal operations.

Imagine the computer is a helper robot that needs to clean up a messy row of letters written on a long piece of paper. The robot walks down the row from left to right one letter at a time. When the robot sees a regular letter, it remembers where that letter lives by putting a sticky note on it. If the robot sees a star, that is a special signal to erase something. The star acts like a magic eraser that knows exactly what to do. It looks back at all the letters the robot has already seen and picks the coolest, smallest letter that arrived last, then it rubs that letter away along with the star itself. Once the robot finishes walking to the very end of the line, it gathers up all the letters that did not get erased and puts them together to show you the final secret message.

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

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