LeetCode 题解工作台
不同字符的最小子序列
返回 s 字典序最小的 子序列 ，该子序列包含 s 的所有不同字符，且只包含一次。 示例 1： 输入： s = "bcabc" 输出 ： "abc" 示例 2： 输入： s = "cbacdcbc" 输出： "acdb" 提示： 1 s 由小写英文字母组成 注意： 该题与 316 https://l…
4
题型
5
代码语言
3
相关题
当前训练重点
中等 · 栈·状态
答案摘要
我们用一个数组 记录字符串 每个字符最后一次出现的位置，用栈来保存结果字符串，用一个数组 或者一个整型变量 记录当前字符是否在栈中。 遍历字符串 ，对于每个字符 ，如果 不在栈中，我们就需要判断栈顶元素是否大于 ，如果大于 ，且栈顶元素在后面还会出现，我们就将栈顶元素弹出，将 压入栈中。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 栈·状态 题型思路
题目描述
返回 s 字典序最小的子序列，该子序列包含 s 的所有不同字符，且只包含一次。
示例 1：
输入：s = "bcabc"输出："abc"
示例 2：
输入：s = "cbacdcbc"输出："acdb"
提示：
1 <= s.length <= 1000s由小写英文字母组成
注意：该题与 316 https://leetcode.cn/problems/remove-duplicate-letters/ 相同
解题思路
方法一：栈
我们用一个数组 记录字符串 每个字符最后一次出现的位置，用栈来保存结果字符串，用一个数组 或者一个整型变量 记录当前字符是否在栈中。
遍历字符串 ，对于每个字符 ，如果 不在栈中，我们就需要判断栈顶元素是否大于 ，如果大于 ，且栈顶元素在后面还会出现，我们就将栈顶元素弹出，将 压入栈中。
最后将栈中元素拼接成字符串作为结果返回。
时间复杂度 ，空间复杂度 。其中 是字符串 的长度。
class Solution:
def smallestSubsequence(self, s: str) -> str:
last = {c: i for i, c in enumerate(s)}
stk = []
vis = set()
for i, c in enumerate(s):
if c in vis:
continue
while stk and stk[-1] > c and last[stk[-1]] > i:
vis.remove(stk.pop())
stk.append(c)
vis.add(c)
return "".join(stk)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Look for a solution that efficiently uses a stack to maintain order.
- question_mark
Ensure that the candidate tracks character occurrences and pops characters from the stack when appropriate.
- question_mark
Candidates should avoid brute-force solutions and focus on a greedy, stack-based approach.
常见陷阱
外企场景- error
Failing to check if a character can still appear later, which can result in an incorrect subsequence.
- error
Not managing the stack in lexicographical order, leading to suboptimal solutions.
- error
Inefficient handling of character occurrences, which may lead to unnecessary operations and higher time complexity.
进阶变体
外企场景- arrow_right_alt
Handle the case where the string contains all unique characters.
- arrow_right_alt
Optimize for strings with large character repetitions.
- arrow_right_alt
Extend the solution to handle strings with uppercase letters or non-alphabetic characters.