316. Remove Duplicate Letters
Given a string which contains only lowercase letters, remove duplicate letters so that every letter appears once and only once. You must make sure your result is the smallest in lexicographical order among all possible results.
Example 1
Input: "bcabc"
Output: "abc"
Example 2
Input: "cbacdcbc"
Output: "acdb"
题意： 这道题是让我们删除一个字符串中的重复元素，使得所有字母只出现过依次。并且要求字符串在删除重复元素之后，字母序是最小的。 需要先统计一下所有字母出现过的次数。 这样就可以遍历整个字符串，判断当前字母是否能够取代结果串的最后一位从而获得一个最优解。但是这样做的前提必须是前一位的字母在之后还出现过。 同时需要一个 used 数组记录是否用过当前的字母。如果用过的话直接跳过就好了。
代码
class Solution {
public String removeDuplicateLetters(String text) {
int[] count= new int[26];
boolean[] used= new boolean[26];
for(char c:text.toCharArray())
count[c-'a']++;
StringBuilder sb= new StringBuilder();
for(char c: text.toCharArray()){
count[c-'a']--;
//If already used we dont have to worry and continue;
if(used[c-'a'])
continue;
//If not used yet, then see if the earlier one is a larger character, and if we have one, then see if we have that character coming down the line using count, and remove it from the current string;
while(sb.length()!=0 && sb.charAt(sb.length()-1)>c && count[sb.charAt(sb.length()-1)-'a']>0){
used[sb.charAt(sb.length()-1)-'a'] = false;
sb.deleteCharAt(sb.length()-1);
}
sb.append(c);
used[c-'a'] = true;
}
return sb.toString();
}
}