LeetCode 字典序最小子序列题解

LeetCode 字典序最小子序列题解

题目描述

给定一个字符串 s，移除重复字符，使得每个字符只出现一次，并且返回字典序最小的结果。

示例：

输入：s = "bcabc"
输出："abc"

解题思路

方法：贪心

思路：

• 统计每个字符出现的次数。
• 遍历字符串，使用栈来维护结果。
• 如果当前字符比栈顶字符小，并且栈顶字符在后面还会出现，则弹出栈顶字符。
• 将当前字符加入结果。

复杂度分析：

• 时间复杂度：O(n)。
• 空间复杂度：O(1)。

代码实现

def smallest_subsequence(s): count = {} in_stack = set() stack = [] for char in s: count[char] = count.get(char, 0) + 1 for char in s: count[char] -= 1 if char in in_stack: continue while stack and char < stack[-1] and count[stack[-1]] > 0: removed = stack.pop() in_stack.remove(removed) stack.append(char) in_stack.add(char) return ''.join(stack) # 测试 def test_smallest_subsequence(): s = "bcabc" print(smallest_subsequence(s)) # 输出："abc" if __name__ == "__main__": test_smallest_subsequence()

总结

字典序最小子序列是贪心算法的典型应用，通过栈来维护结果，确保字典序最小。