Removing Stars From a String
Apply every star, which erases itself and the closest remaining letter to its left, in one pass by pushing letters onto a stack and popping on each star.
Problem Understanding
Removing Stars From a String (LeetCode 2390): given a string s of lowercase letters and stars *, repeatedly choose a star, remove the closest non-star character to its left, and remove the star itself. Return the string once every star is gone. The input always allows this, and the result is unique.
Examples: "leet**cod*e" → "lecoe"; "erase*****" → "".
The Intuition: A Star Is a Backspace
Type the string into a text box where * is the backspace key. Each backspace deletes the last character still on screen.
- Keep a stack of the characters on screen.
- A letter is typed: push it.
- A star is a backspace: pop the top.
The stack, read bottom to top, is the final text. It is the same push-or-pop scan as Remove All Adjacent Duplicates in String, with a simpler rule for when to pop.
Interactive Walkthrough
EMPTY STACK
s
0
1
2
3
4
5
6
7
8
9
10
kept characters (stack, top on the right)
EMPTY
kept
0
Answer
:
Start with an empty stack of kept characters
Next
s[0] = 'l': push it
s
The character being read is filled, and erased characters are struck through. The stack below has its top on the right; a popped character shows in red for one step. Try Nested, where two stars in a row erase two letters.
Dry Run Table
Input: s = "leet**cod*e".
| Read | Action | Stack |
|---|---|---|
| l, e, e, t | push each | l e e t |
| * | pop t | l e e |
| * | pop e | l e |
| c, o, d | push each | l e c o d |
| * | pop d | l e c o |
| e | push | l e c o e |
Answer: "lecoe".
The Solution Template
One pass with a stack of characters. The C version reuses the input array as the stack, with top as the write index.
Removing Stars From a String Code
1var removeStars = function(s) {2 const stack = [];3 for (const ch of s) {4 if (ch === '*') {5 stack.pop();6 } else {7 stack.push(ch);8 }9 }10 return stack.join('');11};
Edge Cases & Common Mistakes
- Everything erased:
"erase*****"leaves an empty string, so return "". - No stars: the stack holds the whole string.
- Building the answer with string concatenation and slicing: removing the last character of an immutable string copies it, making the scan O(n²); use a list or builder.
- Removing the closest character to the right: the star erases to its left only.
Summary
Treat each star as a backspace: push letters onto a stack, pop on stars, and join the stack. O(n) time, O(n) space (O(1) extra when the string can be edited in place).
More practice: DSA interview questions with answers · patterns cheat sheet