难度: Medium
返回 s 字典序最小的子序列，该子序列包含 s 的所有不同字符，且只包含一次。
示例 1：
输入：s = "bcabc"输出："abc"
示例 2：
输入：s = "cbacdcbc"输出："acdb"
提示：
1 <= s.length <= 1000s由小写英文字母组成
注意：该题与 316 https://leetcode.cn/problems/remove-duplicate-letters/ 相同
Submission
运行时间: 24 ms
内存: 16.0 MB
class Solution:
def smallestSubsequence(self, s: str) -> str:
stack = []
seen = set()
last_occurrence = {c: i for i, c in enumerate(s)}
for i, c in enumerate(s):
if c not in seen:
while stack and c < stack[-1] and i < last_occurrence[stack[-1]]:
seen.discard(stack.pop())
seen.add(c)
stack.append(c)
return "".join(stack)
Explain
该解法使用贪心算法和栈来解决问题。首先，通过遍历字符串s建立每个字符的最后出现位置的哈希表，这有助于确定字符是否可以从栈中弹出。算法遍历字符串s中的每个字符，使用栈来构建最终的结果序列。如果当前字符未在结果序列中，且当前字符字典序小于栈顶字符，并且栈顶字符在后面还会出现，那么栈顶字符会被弹出。这保证了序列尽可能地小在字典序中。使用集合seen来跟踪哪些字符已经被加入到栈中，防止重复添加字符。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def smallestSubsequence(self, s: str) -> str:
stack = [] # 初始化栈
seen = set() # 初始化已见字符集合
last_occurrence = {c: i for i, c in enumerate(s)} # 创建字符的最后位置哈希表
for i, c in enumerate(s):
if c not in seen: # 如果字符未在seen中
while stack and c < stack[-1] and i < last_occurrence[stack[-1]]: # 字典序比较和位置判断
seen.discard(stack.pop()) # 弹出元素并从seen中移除
seen.add(c) # 将当前字符添加到seen集合中
stack.append(c) # 字符推入栈中
return ''.join(stack) # 将栈中字符连接成字符串作为结果
Explore
在构建哈希表时，我们遍历整个字符串，并用字典来记录每个字符的索引位置。每次遇到一个字符，都将其在字典中的值更新为当前的索引。这意味着，对于每个字符，最终存储的索引将是该字符在字符串中最后一次出现的位置。因为每次字符再次出现时，其索引值会被新的（较大的）索引值覆盖，从而确保了记录的是最后的位置。
算法中使用了一个哈希表（last_occurrence）来记录每个字符最后一次出现的位置。当考虑是否应该从栈中弹出栈顶字符时，我们可以查看当前字符的索引（i）和栈顶字符的最后出现索引（从哈希表中获取）。如果栈顶字符的最后出现位置大于当前字符的索引，这表明栈顶字符在字符串中后面的位置还会再次出现，因此可以安全地将其从栈中移除，以便在后续适当的位置重新加入。
如果当前字符的字典序小于栈顶元素，并且栈顶元素后面还会出现，则弹出栈顶元素可以帮助我们获得更小的字典序结果。这是因为移除栈顶元素后，我们有机会在结果中以更小的字符替代它，从而达到字典序更小的目的。此操作不会导致最终结果不是最小字典序，因为每次操作都是在确认栈顶元素将来还会出现的情况下进行，这保证了不会丢失任何字符，同时可以尽可能地构造出字典序最小的结果。
seen集合确保每个字符在最终结果子序列中只出现一次。如果一个字符已经在seen集合中，这意味着它已经在栈（也即是最终结果子序列）中。再次将其添加到栈中将会违反结果子序列中字符的唯一性要求。因此，一旦字符加入seen集合，我们就不再将它添加到栈中，除非它之前从栈中被移除（这种情况下该字符也会从seen集合中移除）。