题目描述:
给定一个仅包含小写字母的字符串,去除字符串中重复的字母,使得每个字母只出现一次。需保证返回结果的字典序最小(要求不能打乱其他字符的相对位置)。
示例 1:
输入: “bcabc”
输出: “abc”
示例 2:
输入: “cbacdcbc”
输出: “acdb”
用栈来解决,需要注意的是,每次遍历一个字母时,我们首先看是否已经放入,如果已经有了忽略,如果没有并且栈比顶小,并且栈顶字母后面还会出现,那么我们弹出栈顶,并且设置栈顶元素没有放入,继续遍历,接着我们判断当前字母是否在栈里面存在,如果存在那么就不需要放入了,但是要将次数减一,然后继续循环,如果没有那么设置已经存在,然后入栈。
代码:
class Solution {
public String removeDuplicateLetters(String s) {
int []tem = new int[26];
for (int i = 0; i < s.length(); i++) {
char tems = s.charAt(i);
tem[tems - 'a'] ++;
}
boolean visited[] = new boolean[26];
Stack<Character> stack = new Stack<>();
for (int i = 0; i < s.length(); i++) {
char get = s.charAt(i);
while (!stack.isEmpty() && stack.peek() > get
&& !visited[get - 'a']
&& tem[stack.peek() - 'a'] > 0
) {
visited[stack.peek() - 'a'] = false;
stack.pop();
}
if(visited[get - 'a']){
tem[get - 'a'] --;
continue;
}
visited[get - 'a'] = true;
stack.push(get);
tem[get - 'a'] --;
}
StringBuilder sBuilder = new StringBuilder();
while (!stack.isEmpty()) {
sBuilder.append(stack.pop());
}
return sBuilder.reverse().toString();
}
}