1147MediumStringStackSimulation

Rubbing Letters Off the Tape

Tracked in this browser only

Trains the technique from

LeetCode 2390Removing Stars From a String

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A tape tape holds lowercase letters and the character *.

Working from left to right, each * rubs itself out along with the nearest letter still standing to its left.

Return what the tape reads once every * has been dealt with. The tape always leaves a letter for each * to rub out.

Examples

Example 1

Input: tape = "abc*d*e"
Output: "abe"

The first star rubs out the c and the second rubs out the d, leaving the a, the b and the e.

Example 2

Input: tape = "aaa***"
Output: ""

Each of the three stars rubs out one of the three letters, so nothing is left.

Example 3

Input: tape = "xy*z"
Output: "xz"

The star rubs out the y, and the x and the z close up together.

Constraints

1 <= tape.length <= 10^5
every character of tape is a lowercase English letter or *
the tape always leaves a letter for each star to rub out

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def remove_stars(tape: str) -> str:

Java

public String removeStars(String tape)

The intended approach

Time O(n) over the tape.Space O(n) for the survivors.

Each `*` reaches for the nearest surviving letter to its left, which is the most recently added one that has not already been rubbed out. That is exactly what a pile gives: pushing letters on as they come and pulling one off for each `*`. So walk the tape once with a growing list of survivors. A letter joins the end of the list; a `*` drops whatever is at the end. Nothing needs re-scanning, because the end of the list always names the letter a `*` would reach. Joining the survivors at the finish keeps the whole thing to one pass.

Pythonentry point: remove_stars

def remove_stars(tape):
    kept = []
    for ch in tape:
        if ch == "*":
            kept.pop()
        else:
            kept.append(ch)
    return "".join(kept)

The obvious version

Hunt down the first `*` on the tape, cut it out along with the character just before it, and start hunting again on the shorter tape, until no `*` is left. Costs a fresh copy of the tape for every star.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_remove_stars(tape):
    text = tape
    spot = text.find("*")
    while spot >= 0:
        text = text[:spot - 1] + text[spot + 1:]
        spot = text.find("*")
    return text

How this problem was checked

Reference solution executed against 15 test cases — 15 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in