Removing Stars From a String

Removing Stars From a String

What is this problem about?

The Removing Stars From a String interview question gives you a string containing lowercase letters and * characters. Each * removes the nearest non-star character to its left (like a backspace key). You must process all * characters and return the final resulting string after all deletions are applied. The problem guarantees a valid operation is always possible.

Why is this asked in interviews?

This problem is asked at Goldman Sachs, Microsoft, Amazon, IBM, and Google because it is a clean, practical application of the stack data structure. It mirrors real-world scenarios like text editors with backspace, command-line history, and undo operations. It tests whether candidates instinctively recognize stack usage for "process and undo" patterns in string problems.

Algorithmic pattern used

The pattern is stack simulation. Iterate through each character. If it is a letter, push it onto the stack. If it is *, pop the top of the stack (removing the nearest left character). After processing all characters, join the stack contents to form the result. This runs in O(n) time and O(n) space.

Example explanation

Input: "leet**cod*e"

• l: push. Stack: [l]
• e: push. Stack: [l, e]
• e: push. Stack: [l, e, e]
• t: push. Stack: [l, e, e, t]
• *: pop t. Stack: [l, e, e]
• *: pop e. Stack: [l, e]
• c: push. Stack: [l, e, c]
• o: push. Stack: [l, e, c, o]
• d: push. Stack: [l, e, c, o, d]
• *: pop d. Stack: [l, e, c, o]
• e: push. Stack: [l, e, c, o, e]

Result: "lecoe".

Common mistakes candidates make

• Using a string and calling rstrip or slicing for each *, which is O(n^2) and unnecessary.
• Not handling consecutive * characters correctly — each one pops independently.
• Forgetting to join the stack at the end, returning the list instead of the string.
• Assuming the string always has alternating letters and stars — ** is valid and pops twice.

Interview preparation tip

For the Removing Stars From a String coding problem, the string and stack interview pattern is the optimal approach. The moment you see "remove the nearest left character," think stack. Interviewers at Google and Microsoft appreciate when you immediately name the pattern ("this is a stack problem — push letters, pop on star") before writing code. This problem also has a two-pointer in-place solution for O(1) extra space, which is a strong follow-up to mention.