去除重复字母（LeetCode）

题目

给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证 返回结果的字典序最小（要求不能打乱其他字符的相对位置）。

解题

def removeDuplicateLetters(s):last_occurrence = {ch: i for i, ch in enumerate(s)}  # 记录每个字符最后出现的位置stack = []  # 用于构建结果的栈added = set()  # 记录已经添加到栈中的字符for i, ch in enumerate(s):if ch in added:continue  # 如果字符已经在栈中，跳过while stack and ch < stack[-1] and i < last_occurrence[stack[-1]]:removed_char = stack.pop()  # 移除栈顶字符added.remove(removed_char)  # 从集合中删除移除的字符stack.append(ch)  # 将当前字符压入栈added.add(ch)  # 添加当前字符到集合return ''.join(stack)# 示例用法
s = "cbacdcbc"
result = removeDuplicateLetters(s)
print(result)  # 输出 "acdb"