lexicographically-minimum-string-after-removing-stars

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

You are given a string <code>s</code>. It may contain any number of <code>&#39;*&#39;</code> characters. Your task is to remove all <code>&#39;*&#39;</code> characters.

While there is a <code>&#39;*&#39;</code>, do the following operation:

<ul>
	<li>Delete the leftmost <code>&#39;*&#39;</code> and the smallest non-<code>&#39;*&#39;</code> character to its left. If there are several smallest characters, you can delete any of them.</li>
</ul>

Return the lexicographically smallest resulting string after removing all <code>&#39;*&#39;</code> characters.

&nbsp;
Example 1:

<div class="example-block">
Input: s = &quot;aaba*&quot;

Output: &quot;aab&quot;

Explanation:

We should delete one of the <code>&#39;a&#39;</code> characters with <code>&#39;*&#39;</code>. If we choose <code>s[3]</code>, <code>s</code> becomes the lexicographically smallest.
</div>

Example 2:

<div class="example-block">
Input: s = &quot;abc&quot;

Output: &quot;abc&quot;

Explanation:

There is no <code>&#39;*&#39;</code> in the string.
</div>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= s.length &lt;= 105</code></li>
	<li><code>s</code> consists only of lowercase English letters and <code>&#39;*&#39;</code>.</li>
	<li>The input is generated such that it is possible to delete all <code>&#39;*&#39;</code> characters.</li>
</ul>

clearStars

Lexicographically Minimum String After Removing Stars

Stack

Greedy

Hash Table

String

Heap (Priority Queue)

给你一个字符串&nbsp;<code>s</code>&nbsp;。它可能包含任意数量的&nbsp;<code>'*'</code>&nbsp;字符。你的任务是删除所有的&nbsp;<code>'*'</code>&nbsp;字符。

当字符串还存在至少一个&nbsp;<code>'*'</code>&nbsp;字符时，你可以执行以下操作：

<ul>
	<li>删除最左边的&nbsp;<code>'*'</code>&nbsp;字符，同时删除该星号字符左边一个字典序 最小&nbsp;的字符。如果有多个字典序最小的字符，你可以删除它们中的任意一个。</li>
</ul>

请你返回删除所有&nbsp;<code>'*'</code>&nbsp;字符以后，剩余字符连接而成的 字典序最小 的字符串。

&nbsp;

示例 1：

<div class="example-block">
输入：s = "aaba*"

输出："aab"

解释：

删除 <code>'*'</code>&nbsp;号和它左边的其中一个&nbsp;<code>'a'</code>&nbsp;字符。如果我们选择删除&nbsp;<code>s[3]</code>&nbsp;，<code>s</code>&nbsp;字典序最小。
</div>

示例 2：

<div class="example-block">
输入：s = "abc"

输出："abc"

解释：

字符串中没有&nbsp;<code>'*'</code>&nbsp;字符。
</div>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= s.length &lt;= 105</code></li>
	<li><code>s</code>&nbsp;只含有小写英文字母和&nbsp;<code>'*'</code>&nbsp;字符。</li>
	<li>输入保证操作可以删除所有的&nbsp;<code>'*'</code>&nbsp;字符。</li>
</ul>