2390. Removing Stars From a String
Medium · solved 2026-10-01 · Open on LeetCode
stackstring
Time O(n) · Space O(n)
How to get there
The last letter kept is the first removed
1. Remove the stars by hand, one character at a time. On “leet**cod*e”: read l, e, e, t, then a star. It removes t, the closest letter to its left. The next star removes the second e. Every time a letter is read, there is no way to know yet whether a later star will remove it.
2. Find what must be carried across that gap. Every letter kept so far, in order, because any of them may still be removed.
3. Notice which kept letter a star removes. Always the most recent one still there: last kept, first removed. That is exactly what a stack does: push each letter, and a star pops the top. A star never meets an empty stack, because the problem guarantees every operation is possible.
4. Read off the answer. Whatever is left on the stack, bottom to top, is the string after all stars. The order in which stars are applied doesn’t change the result, so applying them as they arrive gives it in one pass.
The reusable recipe: when a later element cancels the most recent surviving earlier one, keep the survivors on a stack.
Let the variables' meanings write the branches
| Variable | Always means |
|---|---|
stack |
the letters read so far that no star has removed, left to right |
| Character | What it means | What must change | Code |
|---|---|---|---|
* |
remove the closest kept letter to its left | that letter is the top of the stack | stack.pop() |
| letter | one more letter kept, for now | it goes on top | stack.append(token) |
When the loop ends, stack is the answer by its own meaning, so "".join(stack) returns it.
The method carries over: once the stack means “the survivors so far”, each kind of input either adds a survivor or removes the newest one.
Alternatives compared
| Approach | Time | Space | How it works |
|---|---|---|---|
| Edit the string | O(n²) | O(n) | Find a star, cut it and the letter before it, repeat; each cut copies the rest of the string. |
| Stack (chosen) | O(n) | O(n) | Push each letter; a star pops the top. The stack ends as the answer. |
| Write index | O(n) | O(n) | Copy s to a list and keep a write position: a letter is written there and the position moves right, a star moves it back one. The answer is the list up to the position. |
| Scan from the right | O(n) | O(n) | Walk backwards counting pending stars; a letter is kept only when none are pending, otherwise it uses one up. Reverse what was kept. |
All but the first are one pass. The stack states the rule most directly; the write index is the same idea with the stack stored inside the copied list.
solution.py
class Solution:
def removeStars(self, s: str) -> str:
stack = []
for token in s:
if token == "*":
stack.pop()
else:
stack.append(token)
return "".join(stack)Notes
Write your approach, insights, and mistakes here. Any other file in this folder (e.g. solution.py, attempt-1.py) is rendered below as code.