What is the best approach to handle consecutive '*' in this problem?

Using a stack ensures each '*' removes the immediate preceding character, even for multiple consecutive stars, maintaining the correct order.

How do I ensure the result is lexicographically minimal?

Always remove the last character in the current stack when encountering a '*', so the remaining string preserves the smallest order.

Can I solve this without a stack?

A stack is the simplest way to manage state efficiently. Using string concatenation or repeated slicing leads to higher time complexity.

What are the constraints on string length and characters?

The string length is 1 to 10^5, consisting only of lowercase English letters and '*', guaranteeing all '*' can be removed.

How does stack-based state management help in this LeetCode problem?

It tracks the current sequence of letters, allowing immediate removal upon seeing '*', and ensures the resulting string is lexicographically minimal.

#3170

Medium

auto_awesome栈·状态

LeetCode 题解工作台

删除星号以后字典序最小的字符串

给你一个字符串 s 。它可能包含任意数量的 '*' 字符。你的任务是删除所有的 '*' 字符。当字符串还存在至少一个 '*' 字符时，你可以执行以下操作：删除最左边的 '*' 字符，同时删除该星号字符左边一个字典序最小的字符。如果有多个字典序最小的字符，你可以删除它们中的任意一个。请你返回…

哈希表字符串栈贪心堆（优先队列）

题目描述

给你一个字符串 s 。它可能包含任意数量的 '*' 字符。你的任务是删除所有的 '*' 字符。

当字符串还存在至少一个 '*' 字符时，你可以执行以下操作：

删除最左边的 '*' 字符，同时删除该星号字符左边一个字典序最小的字符。如果有多个字典序最小的字符，你可以删除它们中的任意一个。

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

示例 1：

输入：s = "aaba*"

输出："aab"

解释：

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

示例 2：

输入：s = "abc"

输出："abc"

解释：

字符串中没有 '*' 字符。

提示：

1 <= s.length <= 10⁵
s 只含有小写英文字母和 '*' 字符。
输入保证操作可以删除所有的 '*' 字符。

lightbulb

解题思路

方法一：按字符记录下标

我们定义一个数组 $g$ ，用于记录每个字符的下标列表，定义一个长度为 $n$ 的布尔数组 $rem$ ，用于记录每个字符是否需要删除。

遍历字符串 $s$ ：

如果当前字符是星号，我们就需要删除它，因此我们将 $rem[i]$ 标记为已删除。同时，我们需要删除此时字典序最小且下标最大的字符。我们从小到大遍历 $26$ 个小写字母，如果 $g[a]$ 不为空，我们就删除 $g[a]$ 中的最后一个下标，并将 $rem$ 中对应的下标置为已删除。

如果当前字符不是星号，我们就将当前字符的下标加入 $g$ 中。

最后，我们遍历 $s$ ，将未删除的字符拼接起来即可。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

class Solution:
    def clearStars(self, s: str) -> str:
        g = defaultdict(list)
        n = len(s)
        rem = [False] * n
        for i, c in enumerate(s):
            if c == "*":
                rem[i] = True
                for a in ascii_lowercase:
                    if g[a]:
                        rem[g[a].pop()] = True
                        break
            else:
                g[c].append(i)
        return "".join(c for i, c in enumerate(s) if not rem[i])

speed

复杂度分析

指标	值
时间	complexity is O(n * \|Σ\|) because each character is pushed or popped once and comparisons may involve the alphabet size. Space complexity is O(n + \|Σ\|) for the stack and hash tables used to track character frequencies or positions.
空间	O(n +

psychology

面试官常问的追问

外企场景

question_mark
Expect candidates to manage stack operations accurately under '*' deletions.
question_mark
Look for awareness of lexicographical order when deciding which characters to remove.
question_mark
Check that the solution scales efficiently with large strings up to length 10^5.

warning

常见陷阱

外企场景

error
Failing to correctly pop the last character for each '*', breaking lexicographical order.
error
Ignoring edge cases where multiple consecutive '*' appear.
error
Attempting to sort after all removals instead of maintaining order during processing.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Return the lexicographically largest string after removing stars using the same pattern.
arrow_right_alt
Allow additional operations such as replacing letters with '*', still requiring minimal result.
arrow_right_alt
Process strings with Unicode characters, maintaining lexicographical ordering and stack logic.

help

常见问题

外企场景

继续练习

#3081 替换字符串中的问号使分数最小 #2813 子序列最大优雅度 #2434 使用机器人打印字典序最小的字符串