不同字符的最小子序列
题目链接描述示例初始代码模板代码
题目链接
https://leetcode-cn.com/problems/smallest-subsequence-of-distinct-characters/
描述
返回字符串 text 中按字典序排列最小的子序列，该子序列包含 text 中所有不同字符一次。
提示：
1 <= text
.length
<= 1000
text 由小写英文字母组成
注意：本题目与
316 https
://leetcode
-cn
.com
/problems
/remove
-duplicate
-letters
/ 相同
示例
示例 1：
输入：
"cdadabcc"
输出：
"adbc"
示例 2：
输入：
"abcd"
输出：
"abcd"
示例 3：
输入：
"ecbacba"
输出：
"eacb"
示例 4：
输入：
"leetcode"
输出：
"letcod"
初始代码模板
class Solution {
public String
smallestSubsequence(String s
) {
}
}
代码
class Solution {
public String
smallestSubsequence(String s
) {
LinkedList
<Character> stack
= new LinkedList<>();
int[] count
= new int[26];
for (int i
= 0; i
< s
.length(); i
++) {
count
[s
.charAt(i
) - 'a']++;
}
boolean[] have
= new boolean[26];
for (int i
= 0; i
< s
.length(); i
++) {
char c
= s
.charAt(i
);
count
[c
- 'a']--;
if (have
[c
- 'a']) {
continue;
}
while (!stack
.isEmpty() && stack
.peek() > c
) {
if (count
[stack
.peek() - 'a'] == 0) {
break;
}
have
[stack
.pop() - 'a'] = false;
}
stack
.push(c
);
have
[c
- 'a'] = true;
}
StringBuilder sbu
= new StringBuilder();
while (!stack
.isEmpty()) {
sbu
.append(stack
.pop());
}
return sbu
.reverse().toString();
}
}
