友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
316. 去除重复字母
给你一个字符串 s，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证 返回结果的字典序最小（要求不能打乱其他字符的相对位置）。
示例 1：
输入：s = "bcabc" 输出："abc"
示例 2：
输入：s = "cbacdcbc" 输出："acdb"
提示：
-
1 <= s.length <= 104 -
s由小写英文字母组成
思路分析
先遍历字符串，统计每个字符的出现次数。然后依次添加，遇到当前字符小于上次字符时，在上次字符在剩余字符串中还有时，则将上述字符“弹出”。循环弹出，直到循环结束。添加当前字符，记录添加状态。
注意，在遍历字符时，向前走一步，则当前字符的次数就要减一。
-
一刷
-
二刷
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
26
27
28
29
30
31
32
33
34
35
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2024-08-16 19:08
*/
public String removeDuplicateLetters(String s) {
if (s == null || s.isEmpty()) {
return s;
}
int[] count = new int[26];
for (char c : s.toCharArray()) {
count[c - 'a']++;
}
boolean[] visited = new boolean[26];
StringBuilder chars = new StringBuilder();
for (char c : s.toCharArray()) {
int idx = c - 'a';
count[idx]--;
if (visited[idx]) {
continue;
}
while (!chars.isEmpty() && chars.charAt(chars.length() - 1) > c) {
int lastIdx = chars.charAt(chars.length() - 1) - 'a';
// 如果已选中的最后一个字符，在后续字符串中没有了，就不能再删除了。
if (count[lastIdx] == 0) {
break;
}
// 否则，删除掉。后面还可以再加进来
chars.deleteCharAt(chars.length() - 1);
visited[lastIdx] = false;
}
chars.append(c);
visited[idx] = true;
}
return chars.toString();
}
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
26
27
28
29
30
31
32
33
34
35
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2025-03-24 20:39:51
*/
public String removeDuplicateLetters(String s) {
char[] chars = s.toCharArray();
int[] count = new int[26];
for (char c : chars) {
count[c - 'a']++;
}
boolean[] added = new boolean[26];
// result 就是一个“单调栈”
StringBuilder result = new StringBuilder();
for (char c : chars) {
int idx = c - 'a';
count[idx]--;
if (added[idx]) {
continue;
}
// 类似单调栈的操作：单调递增栈，遇到小的，则大的出栈
while (!result.isEmpty() && result.charAt(result.length() - 1) > c) {
int lastCharIdx = result.charAt(result.length() - 1) - 'a';
// 如果 result 最后一个字符后续不再出现，则必须保留了。
if (count[lastCharIdx] == 0) {
break;
}
// 否则，删除。后续再遇到了再添加
result.deleteCharAt(result.length() - 1);
added[lastCharIdx] = false;
}
result.append(c);
added[idx] = true;
}
return result.toString();
}