LC316. Remove Duplicate Letters
Given a string which contains only lowercase letters, remove duplicate letters so that every letter appear once and only once. You must make sure your result is the smallest in lexicographical order among all possible results.
Example:
Given "bcabc"
Return "abc"
这题的难点在于如何才能输出最小的按字母排序的字符串。思路是一直维护一个按照字母序排列的栈，首先统计所有字母出现次数，如果一个较大的字母会在之后出现，就从栈中删除这个字母。最后按照出栈的倒序添加到StringBuilder中即可。
public class Solution {
public String removeDuplicateLetters(String s) {
char[] arr = s.toCharArray();
int[] count = new int[26];
for(char c: arr) count[c - 'a']++;
int[] visit = new int[26];
Stack<Character> stack = new Stack<Character>();
// keep stack ascending
for(char c: arr){
count[c - 'a']--;
if(visit[c - 'a'] == 1) continue;
// if a larger char appear later, remove it from stack
while(!stack.isEmpty() && c < stack.peek() && count[stack.peek()-'a'] > 0){
visit[stack.pop()-'a'] = 0;
}
stack.push(c);
visit[c - 'a'] = 1;
} // for c
StringBuilder sb = new StringBuilder();
for(char c: stack){
sb.append(c);
}
return sb.toString();
}
}
时间复杂度O(n).
另外用栈的解法是非常快的。