题意：给定一个字符串，返回去除重复后，安字典顺序最大的字符串
思路：具体见代码注释
思想：双向队列
复杂度：时间O（n)，空间O(n)
class Solution {
public String removeDuplicateLetters(String s) {
//store the last index for each letter
int[] arr = new int[26];
for(int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
arr[c-'a'] = i;
}
//keep track if letter has been added
HashSet<Character> set = new HashSet<>();
Deque<Character> stack = new ArrayDeque<>();
for(int i = 0; i< s.length(); i++) {
char c = s.charAt(i);
//always add letter if not yet added
if(!set.contains(c)) {
//keep removing if previous letter is bigger and the letter is available later
while(!stack.isEmpty() && (stack.peek() > c) && (arr[stack.peek()-'a'] > i)) {
char tmp = stack.pop();
set.remove(tmp);
}
set.add(c);
stack.push(c);
}
}
//append and reverse before return
StringBuilder sb = new StringBuilder();
while(!stack.isEmpty()) {
sb.append(stack.pop());
}
return sb.reverse().toString();
}
}
