Show problems as
Classic problem #3170MediumHash TableStringStackGreedyHeap (Priority Queue)

Lexicographically Minimum String After Removing Stars

Real-world version: Clearing the Markers Off the Strip
Tracked in this browser only
Read Lexicographically Minimum String After Removing Stars on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

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 starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def clear_stars(strip: str) -> str:
Java
public String clearStars(String strip)

More on the same topics