| comments | difficulty | edit_url | tags | ||||
|---|---|---|---|---|---|---|---|
true |
中等 |
|
给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证 返回结果的字典序最小（要求不能打乱其他字符的相对位置）。
示例 1：
输入：s = "bcabc"输出："abc"
示例 2：
输入：s = "cbacdcbc"输出："acdb"
提示：
1 <= s.length <= 104s由小写英文字母组成
注意：该题与 1081 https://leetcode.cn/problems/smallest-subsequence-of-distinct-characters 相同
我们用一个数组 last 记录每个字符最后一次出现的位置，用栈来保存结果字符串，用一个数组 vis 或者一个整型变量 mask 记录当前字符是否在栈中。
遍历字符串
最后将栈中元素拼接成字符串作为结果返回。
时间复杂度
class Solution:
def removeDuplicateLetters(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)class Solution {
public String removeDuplicateLetters(String s) {
int n = s.length();
int[] last = new int[26];
for (int i = 0; i < n; ++i) {
last[s.charAt(i) - 'a'] = i;
}
Deque<Character> stk = new ArrayDeque<>();
int mask = 0;
for (int i = 0; i < n; ++i) {
char c = s.charAt(i);
if (((mask >> (c - 'a')) & 1) == 1) {
continue;
}
while (!stk.isEmpty() && stk.peek() > c && last[stk.peek() - 'a'] > i) {
mask ^= 1 << (stk.pop() - 'a');
}
stk.push(c);
mask |= 1 << (c - 'a');
}
StringBuilder ans = new StringBuilder();
for (char c : stk) {
ans.append(c);
}
return ans.reverse().toString();
}
}class Solution {
public:
string removeDuplicateLetters(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;
}
};func removeDuplicateLetters(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)
}class Solution:
def removeDuplicateLetters(self, s: str) -> str:
count, in_stack = [0] * 128, [False] * 128
stack = []
for c in s:
count[ord(c)] += 1
for c in s:
count[ord(c)] -= 1
if in_stack[ord(c)]:
continue
while len(stack) and stack[-1] > c:
peek = stack[-1]
if count[ord(peek)] < 1:
break
in_stack[ord(peek)] = False
stack.pop()
stack.append(c)
in_stack[ord(c)] = True
return ''.join(stack)func removeDuplicateLetters(s string) string {
count, in_stack, stack := make([]int, 128), make([]bool, 128), make([]rune, 0)
for _, c := range s {
count[c] += 1
}
for _, c := range s {
count[c] -= 1
if in_stack[c] {
continue
}
for len(stack) > 0 && stack[len(stack)-1] > c && count[stack[len(stack)-1]] > 0 {
peek := stack[len(stack)-1]
stack = stack[0 : len(stack)-1]
in_stack[peek] = false
}
stack = append(stack, c)
in_stack[c] = true
}
return string(stack)
}