Removing Stars From a String: Stack Simulation

LeetCode 2390, Removing Stars From a String, is one of the cleanest medium problems in the stack category. Each star in the string acts like a backspace key, removing the closest non-star character to its left. You process the string left to right, and a stack handles all the bookkeeping for you.

The problem

You are given a string s containing lowercase English letters and stars (*). In one operation, you choose a star, remove it, and remove the closest non-star character to its left. You repeat this until no stars remain. Return the resulting string.

The input is guaranteed to always make the operation possible, meaning there will always be a non-star character to the left of every star.

Example: s = "leet**cod*e". The first star (index 4) removes 't'. The second star (index 5) removes the second 'e'. The third star (index 9) removes 'd'. The characters that survive are l, e, c, o, e, giving the result "lecoe".

Why this is a stack problem

Think about what each star does. It removes the most recently added non-star character. That is exactly the LIFO (last-in, first-out) behavior of a stack. When you see a regular character, you push it. When you see a star, you pop the top. The stack always holds the characters that have not been removed yet, in order.

This is the same pattern as a backspace key in a text editor. Each keystroke adds a character, and backspace removes the most recent one. If you have ever solved "Backspace String Compare" (LeetCode 844), you will recognize the same idea here.

The approach: stack simulation

The algorithm is about as simple as it gets:

1. Create an empty stack (a Python list works perfectly).
2. Iterate through each character in the string from left to right.
3. If the character is not a star, push it onto the stack.
4. If the character is a star, pop the top element from the stack. This removes the closest non-star character to the left.
5. When you have processed every character, join the stack into a string. That is your answer.

The key insight is that you never need to "look back" through the string to find which character to remove. The stack always has the right character on top. That is what makes this O(n) instead of something slower.

Visual walkthrough

Notice the pattern. Non-star characters accumulate on the stack, and each star peels off the most recent one. Consecutive stars (like the two after "leet") peel off multiple characters in a row. At the end, whatever remains on the stack is the answer.

The solution

def removeStars(s):
    stack = []
    for c in s:
        if c == '*':
            stack.pop()
        else:
            stack.append(c)
    return ''.join(stack)

This solution is minimal and complete. Here is what each part does:

• stack = [] initializes an empty list to use as a stack.
• The for loop processes every character exactly once, left to right.
• if c == '*' checks whether the current character is a star. If so, stack.pop() removes the most recent character. If not, stack.append(c) saves the character for the result.
• ''.join(stack) converts the remaining characters back into a string. The stack preserves the original left-to-right order because we always push to the end and pop from the end.

Complexity analysis

The building blocks

Stack for undo/backspace operations

Whenever an operation "cancels" or "removes" the most recent item, a stack is the right data structure. The star in this problem acts exactly like a backspace key. You type characters one by one, and the backspace deletes the last one you typed. A stack models this perfectly because the last character you pushed is always the one on top, ready to be popped.

This same undo/backspace pattern shows up in several other problems:

• Valid Parentheses (LeetCode 20): Each closing bracket matches the most recently opened bracket. Push openers, pop when you see a closer.
• Backspace String Compare (LeetCode 844): Identical idea to this problem. The # character acts as backspace, removing the most recent character.
• Daily Temperatures (LeetCode 739): A monotonic stack variation where you pop elements that have been "resolved" by a newer, warmer temperature.

The common thread is the phrase "closest to the left" or "most recent." When you see those words in a problem description, think stack.

Edge cases

• No stars. The stack collects all characters. Return the original string unchanged.
• All stars cancel all characters. Every character gets popped. Return an empty string. For example, "abc***" becomes "".
• Consecutive stars. Each star pops the most recent remaining character. "abc***" pops c, then b, then a, leaving an empty stack.
• Stars at the end. "abcde**" pops e and d, leaving "abc".
• Alternating characters and stars. "a*b*c" pops a, then pops b, leaving just "c".

From understanding to recall

This problem is one of the cleanest stack problems on LeetCode. The pattern is simple: push non-stars, pop on stars, join the result. There are no tricky edge cases, no off-by-one errors, and no complex comparisons. The real interview value is recognizing that "remove the nearest non-star character to its left" always means stack.

Practice until you see the words "nearest" or "closest to the left" and immediately think stack. The code itself is only a few lines, but producing it confidently under pressure requires having written it before. Spaced repetition turns this pattern from something you understand into something you can recall and write from scratch without hesitation.

Related posts

• Valid Parentheses - The classic stack matching problem with brackets
• Daily Temperatures - Monotonic stack for the next-greater-element pattern
• Evaluate Reverse Polish Notation - Stack-based expression evaluation