class Solution {
public:
string removeDuplicateLetters(string s) {
}
};
316. 去除重复字母
给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证 返回结果的字典序最小（要求不能打乱其他字符的相对位置）。
示例 1：
输入：s = "bcabc"输出："abc"
示例 2：
输入：s = "cbacdcbc"输出："acdb"
提示：
1 <= s.length <= 104s 由小写英文字母组成
注意：该题与 1081 https://leetcode.cn/problems/smallest-subsequence-of-distinct-characters 相同
原站题解
python3 解法, 执行用时: 48 ms, 内存消耗: 14.9 MB, 提交时间: 2022-12-07 18:08:50
class Solution:
def removeDuplicateLetters(self, s) -> int:
stack = []
seen = set()
remain_counter = collections.Counter(s)
for c in s:
if c not in seen:
while stack and c < stack[-1] and remain_counter[stack[-1]] > 0:
seen.discard(stack.pop())
seen.add(c)
stack.append(c)
remain_counter[c] -= 1
return ''.join(stack)
golang 解法, 执行用时: 0 ms, 内存消耗: 1.9 MB, 提交时间: 2022-12-07 18:07:38
func removeDuplicateLetters(s string) string {
left := [26]int{}
for _, ch := range s {
left[ch-'a']++
}
stack := []byte{}
inStack := [26]bool{}
for i := range s {
ch := s[i]
if !inStack[ch-'a'] {
for len(stack) > 0 && ch < stack[len(stack)-1] {
last := stack[len(stack)-1] - 'a'
if left[last] == 0 {
break
}
stack = stack[:len(stack)-1]
inStack[last] = false
}
stack = append(stack, ch)
inStack[ch-'a'] = true
}
left[ch-'a']--
}
return string(stack)
}
javascript 解法, 执行用时: 80 ms, 内存消耗: 43.2 MB, 提交时间: 2022-12-07 18:07:19
/**
* @param {string} s
* @return {string}
*/
var removeDuplicateLetters = function(s) {
const vis = new Array(26).fill(0);
const num = _.countBy(s);
const sb = new Array();
for (let i = 0; i < s.length; i++) {
const ch = s[i];
if (!vis[ch.charCodeAt() - 'a'.charCodeAt()]) {
while (sb.length > 0 && sb[sb.length - 1] > ch) {
if (num[sb[sb.length - 1]] > 0) {
vis[sb[sb.length - 1].charCodeAt() - 'a'.charCodeAt()] = 0;
sb.pop();
} else {
break;
}
}
vis[ch.charCodeAt() - 'a'.charCodeAt()] = 1;
sb.push(ch);
}
num[ch]--;
}
return sb.join('');
};
java 解法, 执行用时: 1 ms, 内存消耗: 40.3 MB, 提交时间: 2022-12-07 18:06:57
class Solution {
public String removeDuplicateLetters(String s) {
boolean[] vis = new boolean[26];
int[] num = new int[26];
for (int i = 0; i < s.length(); i++) {
num[s.charAt(i) - 'a']++;
}
StringBuffer sb = new StringBuffer();
for (int i = 0; i < s.length(); i++) {
char ch = s.charAt(i);
if (!vis[ch - 'a']) {
while (sb.length() > 0 && sb.charAt(sb.length() - 1) > ch) {
if (num[sb.charAt(sb.length() - 1) - 'a'] > 0) {
vis[sb.charAt(sb.length() - 1) - 'a'] = false;
sb.deleteCharAt(sb.length() - 1);
} else {
break;
}
}
vis[ch - 'a'] = true;
sb.append(ch);
}
num[ch - 'a'] -= 1;
}
return sb.toString();
}
}