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()总结
字典序最小子序列是贪心算法的典型应用，通过栈来维护结果，确保字典序最小。
