⚡Flashcard Drill➔
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

  1. A stack models the process directly: non-star characters are pushed, and a star pops the top.
  2. Because every star removes the closest surviving character to its left, the stack top is exactly that character.
  3. The guarantee that the operation is always possible means the stack is never empty when a star arrives.
  4. 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 st costs 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.
🎯 Drill This Card Now➔

🧩 Related Stack Problems