Removing Stars From a String

Problem

You are given a string s of lowercase letters and * characters. Each * removes the closest non-star character to its left, and the star itself.

Apply this operation for every star and return the string that remains. The input guarantees every star has a letter to its left to remove. The result is the same 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; repeatedly rebuilding the string 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

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

def removeStars(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

A star only affects the most recently kept letter, which is exactly LIFO (last in, first out) behavior. Scan once, maintaining a stack of letters that have survived so far: push each letter, pop one letter on each *. No lookahead or re-scanning; each character is handled when it is read.

def removeStars(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:

def removeStars(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 repeated string rebuilding. The same shape solves backspace string compare, adjacent-duplicate removal, and valid-parentheses cleanup.