点击获取AI摘要

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

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

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

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

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

示例 1：

输入： s = “aaba*”

输出： “aab”

解释：

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

示例 2：

输入： s = “abc”

输出： “abc”

解释：

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

提示：

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

问题分析

给定一个只包含小写英文字母和星号 '*' 的字符串 s。如果字符串中存在 '*'，则可以执行如下操作：

删除最左侧的 '*' 字符，并同时删除该星号字符左侧字典序最小的一个字符（如果有多个相同的最小字符，可以删除它们中任意一个；为使最终剩余字符串字典序最小，应当优先删除位置更靠右的那个相同字符）。

当所有星号都被删除后，剩余的字符拼接起来即为答案，要求返回该答案字符串，使其在所有可能的删除方案中字典序最小。

关键点：

每遇到一个 '*'，都要从 * 左侧所有未被删去的字母中选出字典序最小、且若有重复则位置最靠右的那个字符，将其删除，并且把 '*' 本身也删除。
最终剩余字符按原来相对顺序拼接，要求拼出的字符串在所有合法操作序列中字典序最小。

由于处理过程中需要：

动态维护“当前可删除”的字符集合，能够快速查到“字典序最小、位置最靠右”的元素；
删除后还要保证剩余字符能高效拼接。

我们可以将此问题拆解为以下几个子问题：

如何动态存储“当前所有未删去的字母”并每次返回“字典序最小且位置最靠右”的字符？
如何在删除节点后，保持能够在最终阶段按原序快速遍历剩余字符？

算法思路

根据问题，提出以下思路：

使用双向链表维护字符的“存活”状态与邻接关系
- 将原字符串 s 的每个字符视作一个节点，节点编号即字符串索引 i（从 0 到 $n-1$ ）。
- 准备两个整型数组 prev[i] 和 next[i]：
  - 初始时 $\text{prev}[i] = i-1$ （若 $i=0$ 则 $\text{prev}[0]=-1$ ）， $\text{next}[i] = i+1$ （若 $i=n-1$ 则 $\text{next}[n-1]=-1$ ）。
- 用布尔数组 deleted[i] 标记节点是否被删除，执行删除时只需在链表中“跳过”该节点（unlink 操作），并将 deleted[i]=True。
使用最小堆（优先队列）动态维护可删除的字母节点
- 堆中只存放普通字母节点，不存放星号。
- 将堆元素定义为三元组 (ch, -i, i)：
  - ch 是字符本身，堆会按字典序升序排序；
  - 第二个键 -i（负索引）用于在多个相同字母并列时，使得堆顶优先弹出索引更大的节点（因为 $-i_1 < -i_2$ 当且仅当 $i_1>i_2$ ）。
  - 第三维 i 用来标识节点真实位置，方便删除。
- 这样，出堆时得到的节点一定是“字典序最小、若相同则索引最大”的字母节点。
- 由于删除操作会使堆中的某些元素“失效”，我们在真正删除时只做 deleted[i]=True，留下“懒删除”的堆元素。当堆顶元素已被标记删除，则继续 pop() 直到遇到未删除节点为止。
遍历字符串并执行删除操作
对 $i$ 从 $0$ 到 $n-1$ 进行遍历：
- 如果 s[i] 是英文字母，则将三元组 (s[i], -i, i) push 进堆；
- 如果 s[i] 是字符 '*'：
  1. 从堆中 pop，跳过所有已标记 deleted[pos]==True 的元素，直到堆顶对应的 $pos$ 未被删除；
  2. 将该 $pos$ 在链表中 unlink，并标记 deleted[pos]=True；
  3. 再将星号自身 i 也在链表中 unlink，标记 deleted[i]=True。
链表 unlink 操作
- 设要删除的节点编号为 pos：
  1
  2
  3
  4
  5
  6
  7
  deleted[pos] = True
  left = prev[pos]
  right = next[pos]
  if left != -1:
  next[left] = right
  if right != -1:
  prev[right] = left
- 这样可以在 $O(1)$ 时间内从链表中将节点摘除，不破坏剩余节点的相对链接关系。
最终拼接剩余字符
- 遍历结束后，所有星号和对应被删除的字母都已在链表中 unlink，并在 deleted[] 中被标记。
- 找到链表的头节点 head：它是第一个满足 prev[head]==-1 且 deleted[head]==False 的索引。
- 从 head 开始，逐次取 cur = head，在结果列表中加入 s[cur]，然后令 cur = next[cur]，直到 cur == -1。
- 拼接得到的字符串即为答案，且保证字典序最小。

时间复杂度

记字符串长度为 $n$ 。
遍历字符串需要 $O(n)$ 时间。
对于每个英文字母节点，我们向最小堆插入一次，共计最多 $n$ 次插入，每次插入复杂度为 $O(\log n)$ ；
对于每个星号 '*'，我们需要从堆中弹出并跳过某些“已删除”节点，最坏情况下一个节点只会在堆中被弹出一次，因此弹出总次数不超过 $n$ ，每次弹出也是 $O(\log n)$ ；
链表 unlink 和标记删除操作均为 $O(1)$ 。

综合可知，总时间复杂度为

$O\bigl(n + n\log n + n\log n + n\bigr) \;=\; O\bigl(n \log n\bigr).$

空间复杂度：

字符串长度为 $n$ ，需要 $O(n)$ 大小的数组 prev、next、deleted；
堆内元素至多 $n$ 个，空间 $O(n)$ ；
最终总空间复杂度为 $O(n)$ 。

代码分解

下面将实现过程拆分为几个模块，并进行详细说明：

初始化链表指针与删除标记
- 构造 prev[] 和 next[] 数组，让它们串成一个完整的双向链表；
- 构造 deleted[] 布尔数组，全部初始化为 False。
遍历字符串并操作堆与链表
- 遇到字母时，将该节点 (ch, -i, i) 压入最小堆；
- 遇到星号时，执行以下步骤：
  1. 从堆中 pop，若堆顶对应位置已经 deleted[pos]==True，则丢弃并继续 pop；
  2. 得到真正未删除的堆顶节点 pos，在链表中 unlink 并 deleted[pos]=True；
  3. 同理将星号自己在链表中 unlink 并 deleted[i]=True。

链表 unlink 函数（可选封装）

def unlink_node(pos, prev, next, deleted):
    deleted[pos] = True
    left = prev[pos]
    right = next[pos]
    if left != -1:
        next[left] = right
    if right != -1:
        prev[right] = left

最终拼接剩余字符
- 找到头结点 head：第一个满足 prev[head]==-1 且 deleted[head]==False；
- 利用 while cur != -1 的循环，通过 next[cur] 遍历，把所有未删字符累到一个列表，最后 ''.join(...) 即可。

代码实现

import heapq

class Solution:
    def clearStars(self, s: str) -> str:
        
        n = len(s)
        
        # 1. 初始化双向链表的 prev 和 next 数组
        prev = [i - 1 for i in range(n)]
        next = [i + 1 for i in range(n)]
        prev[0] = -1
        next[n - 1] = -1
        
        # 2. deleted 标记每个位置是否已经被删除
        deleted = [False] * n
        
        # 3. 最小堆：只存放普通字母节点，元素为 (字符, -索引, 索引)
        heap = []
        
        # 定义一个辅助函数，便于在链表上执行 unlink 操作
        def unlink_node(pos: int):
            """
            从链表中删除节点 pos，并标记 deleted[pos] = True
            """
            deleted[pos] = True
            left = prev[pos]
            right = next[pos]
            if left != -1:
                next[left] = right
            if right != -1:
                prev[right] = left
        
        # 4. 遍历字符串
        for i, ch in enumerate(s):
            if ch != '*':
                # 普通字母，压入堆
                heapq.heappush(heap, (ch, -i, i))
            else:
                # 遇到 '*'，需要删除一个字典序最小且位置最靠右的字母
                while heap:
                    top_ch, neg_pos, pos = heap[0]
                    if deleted[pos]:
                        # 如果堆顶节点已经被删除，弹出并继续
                        heapq.heappop(heap)
                    else:
                        break
                # 现在堆顶就是要删除的节点
                _, _, pos = heapq.heappop(heap)
                unlink_node(pos)    # 删除该字母节点
                unlink_node(i)      # 删除 '*' 本身
        
        # 5. 在链表中找出 head，拼接所有未被删除的字符
        head = 0
        # 找到第一个没有被删除且 prev[head] == -1 的节点作为 head
        while head < n and (deleted[head] or prev[head] != -1):
            head += 1
        
        # 如果 head 越界，说明所有字符都被删除，返回空串
        if head >= n:
            return ""
        
        ans_chars = []
        cur = head
        while cur != -1:
            if not deleted[cur]:
                ans_chars.append(s[cur])
            cur = next[cur]
        
        return "".join(ans_chars)