Leetcode Greedy 316 @ Java－CONY的世界

316. 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"

Given "cbacdcbc"
Return "acdb"

Naive Thinking is that smallest appears first, but there is still some case that , the character is not the smallest should appear first.

It's when the character is the last time to appear in this string.

Therefore, at first we need to have a array to record all character's count. It can help us know whether it's the last time of the character appears.

And we should let it appear in result string. And since we always track the as smallest as possilble.

We can let the left most of that character appear to make the string in the smallest lexicographical order.

We can do it recursively to get our final result.

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