316. Remove Duplicate Letters - jiejackyzhang/leetcode-note GitHub Wiki

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"

Given "cbacdcbc"
Return "acdb"

解题思路为greedy algorithm。 将最小的字母放在左边（它的右边剩余的应包含所有unique letters），如果最小的字母有duplicates，则取最左边的。

因此，每次取第一个unique letter左边的最小的字母，然后将所有重复去掉，对剩余部分做同样的处理，可用recursive方式来解。

public class Solution {
    public String removeDuplicateLetters(String s) {
        int[] cnt = new int[26];
        for(int i = 0; i < s.length(); i++) cnt[s.charAt(i)-'a']++;
        int pos = 0;
        for(int i = 0; i < s.length(); i++) {
            if(s.charAt(i) < s.charAt(pos)) pos = i;
            if(--cnt[s.charAt(i)-'a'] == 0) break;
        }
        return s.length() == 0 ? "" : s.charAt(pos) + removeDuplicateLetters(s.substring(pos+1).replaceAll(""+s.charAt(pos),""));
    }
}