1126MediumHash TableStringStackGreedyHeap (Priority Queue)

Clearing the Markers Off the Strip

Tracked in this browser only

Trains the technique from

LeetCode 3170Lexicographically Minimum String After Removing Stars

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 strip strip holds lowercase letters and the marker character *.

Every marker has to come off the strip, and taking one off also takes off one letter standing to its left. That letter must be one of the smallest letters still standing to the marker's left, and when several of them tie you may take off whichever you please.

Return the smallest word the surviving letters can spell, ordered as a dictionary would. The strip always leaves enough letters for every marker to come off.

Examples

Example 1

Input: strip = "abab*"
Output: "abb"

The smallest letter to the marker's left is a and two of them stand there. Taking off the later one leaves an a nearer the front, which reads smaller.

Example 2

Input: strip = "ab*"
Output: "b"

The smallest letter to the marker's left is a, so it goes off along with the marker.

Example 3

Input: strip = "aabb**"
Output: "bb"

The first marker takes off the later a and the second marker takes off the other one, leaving the two b letters.

Constraints

1 <= strip.length <= 10^5
every character of strip is a lowercase English letter or *
the strip always leaves enough letters for every marker to come off

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 clear_stars(strip: str) -> str:

Java

public String clearStars(String strip)

The intended approach

Time O(n * 26) in the worst case, from hunting the lowest non-empty letter.Space O(n) for the places and the crossings-off.

Which letter a marker takes is forced up to a tie: it must be one of the smallest still standing to its left. So the only freedom is which copy of that smallest letter goes, and that is where the answer is won or lost. Take the latest copy. Two copies of the same letter differ only in where the letters between them end up relative to it, and keeping the earlier copy pushes that letter further towards the front of the surviving word, which can only make it read smaller or leave it unchanged. So walk the strip once holding, for each of the twenty-six letters, the places where its surviving copies stand. A letter joins its own list. A marker crosses itself off, then finds the lowest letter with a non-empty list and crosses off the last place in it, which is the latest copy. At the end, read the strip again keeping only what was never crossed off, which keeps the survivors in their original order.

Pythonentry point: clear_stars

def clear_stars(strip):
    slots = [[] for _ in range(26)]
    gone = [False] * len(strip)
    for i in range(len(strip)):
        ch = strip[i]
        if ch == "*":
            gone[i] = True
            for k in range(26):
                if slots[k]:
                    gone[slots[k].pop()] = True
                    break
        else:
            slots[ord(ch) - 97].append(i)
    out = []
    for i in range(len(strip)):
        if not gone[i]:
            out.append(strip[i])
    return "".join(out)

The obvious version

Search over the choices. Find the first marker, work out the smallest letter to its left, and for every copy of that letter try taking that copy off along with the marker, then solve the shorter strip and keep whichever answer reads smallest. Strips already worked out are remembered so none is redone.

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_clear_stars(strip):
    known = {}

    def solve(text):
        if text in known:
            return known[text]
        spot = text.find("*")
        if spot < 0:
            known[text] = text
            return text
        low = None
        for i in range(spot):
            if low is None or text[i] < low:
                low = text[i]
        answer = None
        for i in range(spot):
            if text[i] == low:
                got = solve(text[:i] + text[i + 1:spot] + text[spot + 1:])
                if answer is None or got < answer:
                    answer = got
        known[text] = answer
        return answer

    return solve(strip)

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