NeetCode #352LC-2390MediumStack
← Back to All Problems#352 · #2390 · Removing Stars From a String(从字符串中移除星号)
📌 Problem Statement & Constraints
You are given a string
s containing stars *. In one operation you may remove a star and the closest non-star character to its left. Repeat until no stars remain, and return the resulting string. Constraints: 1 <= s.length <= 10^5; the input guarantees the operation is always possible.💡 Core Algorithmic Approaches
- A stack models the process directly: non-star characters are pushed, and a star pops the top.
- Because every star removes the closest surviving character to its left, the stack top is exactly that character.
- The guarantee that the operation is always possible means the stack is never empty when a star arrives.
- The result is the stack joined.
💻 Benchmark Python3 Implementation
class Solution:
def removeStars(self, s: str) -> str:
st = []
for ch in s:
if ch == "*":
st.pop() # remove the closest survivor to the left
else:
st.append(ch)
return "".join(st)⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): each character is pushed or popped once.
💾 Space Complexity
O(n) for the stack.
⚠️ Interview Pitfalls & Follow-ups
- Popping without checking for emptiness: the problem guarantees it is safe, but a defensive
if stcosts nothing. - Using
s.replace('*', ''): that removes stars without removing their target characters. - Scanning backwards: also possible, but the forward stack is the natural model.
- Assuming stars are always at the end: they can appear anywhere.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.