/*
* 316. Remove Duplicate Letters
* 2016-7-5 by Mingyang
* 这个题目有一定的难度,所以需要自己再研究一下
* 这里用到了stack,首先没到一个数的时候,计数器减一,然后跟stack里面的比较
* 如果比stack peek的还小,这个就是放到stack里面的前面的,否则就是放到后面了
* 不过注意!!!stack在弹出的时候必须确保有备胎,也就是弹出以后必须有后补才弹
* 不然不要弹!
* 每次弹出来以后需要把visited设为false,每次进去以后呢也需要把visited设为true!!
*/
public String removeDuplicateLetters(String s) {
Stack<Character> stack = new Stack<Character>();
// appearance count
int[] count = new int[26];
// used or not;
boolean[] added = new boolean[26];
// count appearances
for (char ch : s.toCharArray())
count[ch - 'a']++;
// go through each char
for (char ch : s.toCharArray()) {
count[ch - 'a']--;
if (added[ch - 'a'])
continue;
// poping out the char which is bigger and still has some left in behind
while (!stack.isEmpty() && stack.peek() > ch
&& count[stack.peek() - 'a'] > 0)
added[stack.pop() - 'a'] = false;
// add current one
stack.push(ch);
added[ch - 'a'] = true;
}
// move from stack to string
StringBuilder sb = new StringBuilder();
while (!stack.isEmpty()) {
sb.append(stack.pop());
}
return sb.reverse().toString();
}