题目:
给你一个字符串 s
,请你去除字符串中重复的字母,使得每个字母只出现一次。需保证 返回结果的字典序最小(要求不能打乱其他字符的相对位置)。
示例 1:
输入:s = "bcabc"
输出:
"abc"
示例 2:
输入:s = "cbacdcbc"
输出:"acdb"
提示:
1 <= s.length <= 104
s
由小写英文字母组成
class Solution {
public String removeDuplicateLetters(String s) {
int len = s.length();
char[] charArray = s.toCharArray();
int[] lastIndex = new int[26];
for(int i = 0; i < len; i++){
lastIndex[charArray[i] - 'a'] = i;
}
boolean[] visited = new boolean[26];
Deque<Character> stack = new ArrayDeque<>();
for(int i = 0; i < len; i++){
if(visited[charArray[i] - 'a']){
continue;
}
while(!stack.isEmpty() && stack.peekLast() > charArray[i] && lastIndex[stack.peekLast() - 'a']>i){
Character top = stack.removeLast();
visited[top - 'a'] = false;
}
stack.addLast(charArray[i]);
visited[charArray[i] - 'a'] = true;
}
StringBuilder stringBuilder = new StringBuilder();
for(char c : stack){
stringBuilder.append(c);
}
return stringBuilder.toString();
}
}