题目描述
返回 s 字典序最小的子序列，该子序列包含 s 的所有不同字符，且只包含一次。
示例 1：
输入：s = "bcabc"
输出："abc"
示例 2：
输入：s = "cbacdcbc"
输出："acdb"
提示：
1 <= s.length <= 1000s 由小写英文字母组成
注意：该题与 316 https://leetcode.cn/problems/remove-duplicate-letters/ 相同
解法
方法一：栈
我们用一个数组 $last$ 记录字符串 $s$ 每个字符最后一次出现的位置，用栈来保存结果字符串，用一个数组 $vis$ 或者一个整型变量 $mask$ 记录当前字符是否在栈中。
遍历字符串 $s$，对于每个字符 $c$，如果 $c$ 不在栈中，我们就需要判断栈顶元素是否大于 $c$，如果大于 $c$，且栈顶元素在后面还会出现，我们就将栈顶元素弹出，将 $c$ 压入栈中。
最后将栈中元素拼接成字符串作为结果返回。
时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 是字符串 $s$ 的长度。
1
2
3
4
5
6
7
8
9
10
11
12
13 | 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)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 | class Solution {
public String smallestSubsequence(String text) {
int[] cnt = new int[26];
for (char c : text.toCharArray()) {
++cnt[c - 'a'];
}
boolean[] vis = new boolean[26];
char[] cs = new char[text.length()];
int top = -1;
for (char c : text.toCharArray()) {
--cnt[c - 'a'];
if (!vis[c - 'a']) {
while (top >= 0 && c < cs[top] && cnt[cs[top] - 'a'] > 0) {
vis[cs[top--] - 'a'] = false;
}
cs[++top] = c;
vis[c - 'a'] = true;
}
}
return String.valueOf(cs, 0, top + 1);
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25 | class Solution {
public:
string smallestSubsequence(string s) {
int n = s.size();
int last[26] = {0};
for (int i = 0; i < n; ++i) {
last[s[i] - 'a'] = i;
}
string ans;
int mask = 0;
for (int i = 0; i < n; ++i) {
char c = s[i];
if ((mask >> (c - 'a')) & 1) {
continue;
}
while (!ans.empty() && ans.back() > c && last[ans.back() - 'a'] > i) {
mask ^= 1 << (ans.back() - 'a');
ans.pop_back();
}
ans.push_back(c);
mask |= 1 << (c - 'a');
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 | func smallestSubsequence(s string) string {
last := make([]int, 26)
for i, c := range s {
last[c-'a'] = i
}
stk := []rune{}
vis := make([]bool, 128)
for i, c := range s {
if vis[c] {
continue
}
for len(stk) > 0 && stk[len(stk)-1] > c && last[stk[len(stk)-1]-'a'] > i {
vis[stk[len(stk)-1]] = false
stk = stk[:len(stk)-1]
}
stk = append(stk, c)
vis[c] = true
}
return string(stk)
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 | function smallestSubsequence(s: string): string {
const f = (c: string): number => c.charCodeAt(0) - 'a'.charCodeAt(0);
const last: number[] = new Array(26).fill(0);
for (const [i, c] of [...s].entries()) {
last[f(c)] = i;
}
const stk: string[] = [];
let mask = 0;
for (const [i, c] of [...s].entries()) {
const x = f(c);
if ((mask >> x) & 1) {
continue;
}
while (stk.length && stk[stk.length - 1] > c && last[f(stk[stk.length - 1])] > i) {
mask ^= 1 << f(stk.pop()!);
}
stk.push(c);
mask |= 1 << x;
}
return stk.join('');
}
|
方法二