| 题目链接 | 3170. 删除星号以后字典序最小的字符串 |
|---|---|
| 思路 | 堆栈 & 位运算 |
| 题解链接 | 三种写法：26 个栈+位运算优化（Python/Java/C++/Go） |
| 关键点 | 1. 用堆栈跟踪各个字母出现的位置 2. 用位运算跟踪当前最小字母（lowbit技巧） |
| 时间复杂度 | 朴素做法：\(O(n\vert\Sigma\vert)\) 位运算优化：\(O(n+\vert\Sigma\vert)\) |
| 空间复杂度 | 朴素做法：\(O(n+\vert\Sigma\vert)\) 位运算优化：\(O(n+\vert\Sigma\vert)\) |
代码实现（朴素做法）：
class Solution:
def clearStars(self, s: str) -> str:
s = list(s)
stack = [[] for _ in range(26)]
for i, ch in enumerate(s):
if ch != '*':
stack[ord(ch) - ord('a')].append(i)
continue
for positions in stack:
if positions:
s[positions.pop()] = '*'
break
return "".join(ch for ch in s if ch != "*")
代码实现（位运算优化）：
class Solution:
def clearStars(self, s: str) -> str:
s = list(s)
stack = [[] for _ in range(26)]
mask = 0
for i, ch in enumerate(s):
if ch != '*':
ch = ord(ch) - ord('a')
stack[ch].append(i)
mask |= 1 << ch
else:
lowbit = mask & -mask
position = stack[lowbit.bit_length() - 1]
s[position.pop()] = '*'
if not position:
mask ^= lowbit
return "".join(ch for ch in s if ch != '*')