leetcode 316 Remove Duplicate Letters
z
 2019-04-07 21:11:55  

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 1:

1
2
Input: "bcabc"
Output: "abc"

Example 2:

1
2
Input: "cbacdcbc"
Output: "acdb"

先用一个count数组保存每一个字符出现的次数。

然后从左到右遍历count数组，同时保存当前遇到的最小的字符的下表。

每遇到一个新的字符，将count数组中对应的位置减1，如果得到0，说明再往后就不再会出现该字符了，那么就需要把该字符之前的最小的字符保存到返回的string中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public String removeDuplicateLetters(String s) {
        if (s.isEmpty())
            return "";
        int[] count = new int[26];
        for (char c: s.toCharArray()) {
            count[c-'a'] ++;
        }
        int idx = 0;
        for (int i=0; i<s.length(); i++) {
            if (s.charAt(i) < s.charAt(idx)) 
                idx = i;
            if (--count[s.charAt(i) - 'a'] == 0)
                break;
        }
        return s.charAt(idx) + removeDuplicateLetters(s.substring(idx+1).replace(""+s.charAt(idx), ""));
        
    }
}