Removing Stars From a String

Problem

You are given a string s containing lowercase letters and * characters. Every * deletes two things at once: the closest non-star character to its left, and the star itself.

Apply this operation for every star (the input is guaranteed to make this always possible — a star always has a letter to its left to erase) and return the string that remains. The result is unique regardless of the order in which you process the stars.

Examples

Example 1

Input: s = "leet**cod*e" Output: "lecoe" Explanation: the first * erases the closer t, the second * erases the e before it, and the third * erases d; what remains is lecoe.

Example 2

Input: s = "erase*****" Output: "" Explanation: five stars erase all five letters, leaving the empty string.

Example 3

Input: s = "ab*c*" Output: "a" Explanation: the first star removes b, the second star removes c.

Constraints

• 1 <= s.length <= 10^5
• s consists of lowercase English letters and *.
• The operation is always performable — a linear single-pass solution is expected; repeated string surgery is too slow.

Think about it first

TL;DR

Single pass with a stack — push letters, pop on * — O(n) time, O(n) space.

Approach 1 — Brute force

Literally simulate the statement: while the string contains a *, find the first one and rebuild the string without the star and the letter before it.

class Solution:
    def removeStars(self, s: str) -> str:
        while "*" in s:
            i = s.index("*")
            s = s[: i - 1] + s[i + 1 :]
        return s

Complexity: each rebuild copies O(n) characters and there can be O(n) stars, so O(n²) time, O(n) space. With n = 10^5 and a star-heavy input like "a"*50000 + "*"*50000, that’s ~10^9 character copies — far too slow.

Approach 2 — Stack of survivors

The insight: a star only ever affects the most recently kept letter — exactly LIFO (last in, first out) behavior. So scan once, maintaining a stack of letters that have survived so far: a letter pushes itself, a star pops one letter. No lookahead, no re-scanning; each character is handled the moment it’s read.

class Solution:
    def removeStars(self, s: str) -> str:
        stack: list[str] = []
        for ch in s:
            if ch == "*":
                stack.pop()
            else:
                stack.append(ch)
        return "".join(stack)

Walkthrough of Example 1 — s = "leet**cod*e":

Join → "lecoe". Matches the expected output.

Complexity: O(n) time (one push or pop per character, plus one O(n) join), O(n) space for the stack.

A note on the two-pointer variant

The same idea is often taught as an in-place two-pointer overwrite on a character array — a write pointer marks the end of the survivor prefix, and a star just steps it back. It is the identical algorithm; the array prefix is the stack. In Python it saves nothing (strings are immutable), but it’s worth recognizing as the O(1)-extra-space phrasing in languages with mutable strings:

class Solution:
    def removeStars(self, s: str) -> str:
        buf = list(s)
        write = 0
        for ch in s:
            if ch == "*":
                write -= 1
            else:
                buf[write] = ch
                write += 1
        return "".join(buf[:write])

Complexity: O(n) time, O(n) auxiliary space in Python (O(1) extra in a mutable-string language).

Common pitfalls

• Building the answer with repeated string concatenation (res = res[:-1], res += ch) instead of a list — each operation copies the whole string and quietly reintroduces O(n²).
• Trying to process stars right-to-left or “find the star’s left neighbor in the original string” — the neighbor may itself already be deleted; the stack handles this cascading automatically.
• Calling stack.pop() without the problem’s guarantee would crash on inputs like "*a"; here the guarantee makes the unguarded pop safe, but say so in an interview.

Pattern takeaway

When an operation always targets “the most recent surviving element to the left,” you are being told the data structure: a stack. Simulate left to right, letting pushes represent survival and pops represent cancellation — one pass replaces any amount of repeated string surgery. The same shape solves backspace string compare, adjacent-duplicate removal, and valid-parentheses cleanup.