Introduction: What Is LeetCode 2390 Removing Stars From a String?
If you are preparing for coding interviews at companies like Google, Amazon, or Microsoft, LeetCode 2390 Removing Stars From a String is a must-solve problem. It tests your understanding of the stack data structure and string manipulation — two of the most frequently tested topics in technical interviews.
In this article, we will cover:
- What the problem is asking in plain English
- 3 different Java approaches (Brute Force, Stack, StringBuilder)
- Step-by-step dry run with examples
- Time and space complexity for each approach
- Common mistakes to avoid
- FAQs that appear in Google's People Also Ask
Let's dive in!
Problem Statement Summary
You are given a string s containing lowercase letters and stars *. In one operation:
- Choose any
*in the string - Remove the
*itself AND the closest non-star character to its left
Repeat until all stars are removed and return the final string.
Example:
Real Life Analogy — Think of It as a Backspace Key
Imagine you are typing on a keyboard. Every * acts as your backspace key — it deletes itself and the character just before it.
You type "leet" and press backspace twice:
- Backspace 1 → deletes
t→"lee" - Backspace 2 → deletes
e→"le"
That is exactly what this problem simulates! Once you see it this way, the solution becomes very obvious.
Approach 1: Brute Force Simulation (Beginner Friendly)
Idea
Directly simulate the process the problem describes:
- Scan the string from left to right
- Find the first
* - Remove it and the character just before it
- Repeat until no stars remain
Java Code
Time and Space Complexity
| Complexity | Value | Reason |
| Time | O(n²) | Each deletion shifts all remaining characters |
| Space | O(n) | StringBuilder storage |
⚠️ Important Warning
This problem has n up to 100,000. Brute force will get Time Limit Exceeded (TLE) on LeetCode. Use this only to understand the concept, never in production or interviews.
Approach 2: Stack Based Solution (Interview Favorite)
Idea
A stack is the perfect data structure here because:
- We always remove the most recently added letter when a
*appears - That is the definition of Last In First Out (LIFO) — exactly what a stack does
Algorithm:
- Letter → push onto stack
*→ pop from stack (removes closest left character)- At the end, build result from stack contents
Java Code
Step-by-Step Dry Run — "leet**cod*e"
| Step | Character | Action | Stack State |
| 1 | l | push | [l] |
| 2 | e | push | [l,e] |
| 3 | e | push | [l,e,e] |
| 4 | t | push | [l,e,e,t] |
| 5 | * | pop t | [l,e,e] |
| 6 | * | pop e | [l,e] |
| 7 | c | push | [l,e,c] |
| 8 | o | push | [l,e,c,o] |
| 9 | d | push | [l,e,c,o,d] |
| 10 | * | pop d | [l,e,c,o] |
| 11 | e | push | [l,e,c,o,e] |
✅ Final Answer: "lecoe"
Time and Space Complexity
| Complexity | Value | Reason |
| Time | O(n) | Single pass through the string |
| Space | O(n) | Stack holds up to n characters |
Approach 3: StringBuilder as Stack (Optimal Solution) ✅
Idea
This is the best and most optimized approach. A StringBuilder can act as a stack:
append(c)→ works like pushdeleteCharAt(sb.length() - 1)→ works like pop- No reverse needed at the end unlike the Stack approach
Java Code
Step-by-Step Dry Run — "erase*****"
| Step | Character | Action | StringBuilder |
| 1 | e | append | "e" |
| 2 | r | append | "er" |
| 3 | a | append | "era" |
| 4 | s | append | "eras" |
| 5 | e | append | "erase" |
| 6 | * | delete last | "eras" |
| 7 | * | delete last | "era" |
| 8 | * | delete last | "er" |
| 9 | * | delete last | "e" |
| 10 | * | delete last | "" |
✅ Final Answer: ""
Why StringBuilder Beats Stack in Java
| Factor | Stack<Character> | StringBuilder |
| Memory | Boxes char → Character object | Works on primitives directly |
| Reverse needed | Yes | No |
| Code length | More verbose | Cleaner and shorter |
| Performance | Slightly slower | Faster |
Time and Space Complexity
| Complexity | Value | Reason |
| Time | O(n) | One pass, each character processed once |
| Space | O(n) | StringBuilder storage |
All Approaches Comparison Table
| Approach | Time | Space | Passes LeetCode? | Best For |
| Brute Force | O(n²) | O(n) | ❌ TLE | Understanding concept |
| Stack | O(n) | O(n) | ✅ Yes | Interview explanation |
| StringBuilder | O(n) | O(n) | ✅ Yes | Best solution |
How This Relates to LeetCode 3174 Clear Digits
If you have already solved LeetCode 3174 Clear Digits, you will notice this problem is nearly identical:
| Feature | 3174 Clear Digits | 2390 Removing Stars |
| Trigger | Digit 0-9 | Star * |
| Removes | Closest left non-digit | Closest left non-star |
| Difficulty | Easy | Medium |
| Best approach | StringBuilder | StringBuilder |
The exact same solution pattern works for both. This is why learning patterns matters more than memorizing individual solutions!
Common Mistakes to Avoid
1. Not checking sb.length() > 0 before deleting Even though the problem guarantees valid input, always add this guard. It shows clean, defensive coding in interviews.
2. Forgetting to reverse when using Stack Stack gives you characters in reverse order. If you forget .reverse(), your answer will be backwards.
3. Using Brute Force for large inputs With n up to 100,000, O(n²) will time out. Always use the O(n) approach.
FAQs — People Also Ask
Q1. What data structure is best for LeetCode 2390? A Stack or StringBuilder used as a stack is the best data structure. Both give O(n) time complexity. StringBuilder is slightly more optimal in Java because it avoids object boxing overhead.
Q2. Why does a star remove the closest left character? Because the problem defines it that way — think of * as a backspace key on a keyboard. It always deletes the character immediately before the cursor position.
Q3. What is the time complexity of LeetCode 2390? The optimal solution runs in O(n) time and O(n) space, where n is the length of the input string.
Q4. Is LeetCode 2390 asked in Google interviews? Yes, this type of stack simulation problem is commonly asked at Google, Amazon, Microsoft, and Meta interviews as it tests understanding of LIFO operations and string manipulation.
Q5. What is the difference between LeetCode 2390 and LeetCode 844? Both use the same backspace simulation pattern. In 844 Backspace String Compare, # is the backspace character and you compare two strings. In 2390, * is the backspace and you return the final string.
Similar LeetCode Problems to Practice Next
| Problem | Difficulty | Pattern |
| 844. Backspace String Compare | Easy | Stack simulation |
| 1047. Remove All Adjacent Duplicates In String | Easy | Stack simulation |
| 3174. Clear Digits | Easy | Stack simulation |
| 20. Valid Parentheses | Easy | Classic stack |
| 735. Asteroid Collision | Medium | Stack simulation |
Conclusion
LeetCode 2390 Removing Stars From a String is a classic stack simulation problem that every developer preparing for coding interviews should master. The key insight is recognizing that * behaves exactly like a backspace key, which makes a stack or StringBuilder the perfect tool.
Quick Recap:
- Brute force works conceptually but TLEs on large inputs
- Stack solution is clean and great for explaining in interviews
- StringBuilder solution is the most optimal in Java — no boxing, no reversal
