316. 去除重复字母
题目描述
输入一个只由小写英文字母组成的字符串 s。
从中删掉一些字符，使 s 中出现过的每个字母都恰好保留一个。保留下来的字符按原来的先后顺序排列，也就是说结果必须是 s 的子序列。
在所有满足条件的结果中，返回字典序最小的那个。
示例 1
输入：s = "bcabc" 输出："abc"
解释：a、b、c 各留一个，最小的排法是 abc。
示例 2
输入：s = "cbacdcbc" 输出："acdb"
解释：在保持原有先后顺序的前提下，acdb 是字典序最小的结果。
数据范围
1 <= s.length <= 10^4s由小写英文字母组成。
解题思路
想让字典序最小，就希望越靠前的字母越小。从左到右扫描，用栈存放当前答案。来了一个新字母 c 时，如果栈顶字母比 c 大，而且栈顶字母在 c 之后还会再出现，那么现在把它弹掉、以后再放回来，一定能让结果更小，于是不断弹栈；然后把 c 压入。已经在栈里的字母直接跳过，因为它已经待在一个更优的位置上。先预处理每个字母最后出现的下标 last，用来判断“后面还有没有”。
为什么正确
栈中字母互不相同；在“每个已扫过的字母最多出现一次、且还能补齐剩下字母”的前提下，栈是字典序最小的前缀。栈顶字母如果比后来者大，只有当它是最后一次出现时才会被保留。
复杂度分析
时间 O(n)，每个字母最多入栈、出栈各一次；空间 O(Σ)，Σ = 26，栈和 seen 都不超过字母表大小。
易错点
弹栈时要同时把字母从 seen 里移除，否则它以后再出现时会被错误地跳过；而且已经在栈里的字母必须直接跳过、不能触发弹栈，否则可能把唯一保留的那一份弹掉，导致结果缺字母。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def removeDuplicateLetters(self, s: str) -> str:
last = {c: i for i, c in enumerate(s)}
stack = []
seen = set()
for i, c in enumerate(s):
if c in seen:
continue
while stack and stack[-1] > c and last[stack[-1]] > i:
seen.discard(stack.pop())
stack.append(c)
seen.add(c)
return ''.join(stack)class Solution {
public String removeDuplicateLetters(String s) {
int[] last = new int[26];
for (int i = 0; i < s.length(); i++) last[s.charAt(i) - 'a'] = i;
StringBuilder stack = new StringBuilder();
boolean[] seen = new boolean[26];
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (seen[c - 'a']) {
continue;
}
while (stack.length() > 0
&& stack.charAt(stack.length() - 1) > c
&& last[stack.charAt(stack.length() - 1) - 'a'] > i) {
seen[stack.charAt(stack.length() - 1) - 'a'] = false;
stack.deleteCharAt(stack.length() - 1);
}
stack.append(c);
seen[c - 'a'] = true;
}
return stack.toString();
}
}class Solution {
public:
string removeDuplicateLetters(string s) {
int last[26] = {0};
for (int i = 0; i < (int)s.size(); i++) last[s[i] - 'a'] = i;
string stk;
bool seen[26] = {false};
for (int i = 0; i < (int)s.size(); i++) {
char c = s[i];
if (seen[c - 'a']) {
continue;
}
while (!stk.empty() && stk.back() > c && last[stk.back() - 'a'] > i) {
seen[stk.back() - 'a'] = false;
stk.pop_back();
}
stk.push_back(c);
seen[c - 'a'] = true;
}
return stk;
}
};func removeDuplicateLetters(s string) string {
last := [26]int{}
for i := 0; i < len(s); i++ {
last[s[i]-'a'] = i
}
stack := []byte{}
seen := [26]bool{}
for i := 0; i < len(s); i++ {
c := s[i]
if seen[c-'a'] {
continue
}
for len(stack) > 0 && stack[len(stack)-1] > c && last[stack[len(stack)-1]-'a'] > i {
seen[stack[len(stack)-1]-'a'] = false
stack = stack[:len(stack)-1]
}
stack = append(stack, c)
seen[c-'a'] = true
}
return string(stack)
}var removeDuplicateLetters = function(s) {
const last = new Map();
for (let i = 0; i < s.length; i++) last.set(s[i], i);
const stack = [];
const seen = new Set();
for (let i = 0; i < s.length; i++) {
const c = s[i];
if (seen.has(c)) {
continue;
}
while (stack.length && stack[stack.length - 1] > c && last.get(stack[stack.length - 1]) > i) {
seen.delete(stack.pop());
}
stack.push(c);
seen.add(c);
}
return stack.join('');
};function removeDuplicateLetters(s: string): string {
const last: Map<string, number> = new Map();
for (let i = 0; i < s.length; i++) last.set(s[i], i);
const stack: string[] = [];
const seen = new Set();
for (let i = 0; i < s.length; i++) {
const c = s[i];
if (seen.has(c)) {
continue;
}
while (stack.length && stack[stack.length - 1] > c && last.get(stack[stack.length - 1])! > i) {
seen.delete(stack.pop());
}
stack.push(c);
seen.add(c);
}
return stack.join('');
}