#3170

Lexicographically Minimum String After Removing Stars

medium · 51% accepted · 589 likes · top 40%

hash table · string · stack · greedy · heap (priority queue)

Description

You are given a string s. It may contain any number of '*' characters. Your task is to remove all '*' characters.

While there is a '*', do the following operation:

- Delete the leftmost '*' and the smallest non-'*' character to its left. If there are several smallest characters, you can delete any of them.

Return the lexicographically smallest resulting string after removing all '*' characters.

Solution