[LC 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”

两种思路:
1, recursive
搜索最左边的最小的character,如果出现已经错过了某个character所有出现的位置,那么暂停搜索。删除找到的character和它左边所有的character,再来继续重复以上操作.
举例:caccabad
第一步找到a,继续搜索cccbd
第二步找到c,继续搜索bd
第三步找到b,继续搜索d
第四步找到d

    public String removeDuplicateLetters(String s) {
        if (s == null || s.length() == 0) return s;
        int[] count = new int[26];
        for (char c : s.toCharArray()) {
            count[c - 'a']++;
        }
        int pos = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) < s.charAt(pos)) pos = i;
            if (--count[s.charAt(i) - 'a'] == 0) break;
        }
        return s.charAt(pos) + removeDuplicateLetters(s.substring(pos + 1).replaceAll("" + s.charAt(pos), ""));
    }

2,iterative
找到所有字幕最后一次出现的位置,从位置最靠前的开始搜索范围内最小的character。
举例:cbacdcbc
abcd最后出现的位置 [2, 6, 7, 4]
第一步搜索[0, 2],找到’a’,s[2] == ‘a’,end = 4
第二步搜索[3, 4],找到’c’,s[4] != ‘c’,end不变
第三步搜索[4, 4],找到’d’,s[4] == ‘d’,end = 6
第四步搜索[5, 6],找到’b’,s[6] == ‘b’,end = 7
结果长度已经够了,停止搜索

    public String removeDuplicateLetters(String s) {
        int[] lastIndex = new int[26];
        Arrays.fill(lastIndex, -1);
        int len = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (lastIndex[c - 'a'] < 0) len++;
            lastIndex[c - 'a'] = i;
        }
        
        StringBuilder sb = new StringBuilder();
        int start = 0, end = getMin(lastIndex);
        while (sb.length() < len) {
            char minChar = 'z' + 1;
            for (int i = start; i <= end; i++) {
                char c = s.charAt(i);
                if (lastIndex[c - 'a'] >= 0 && c < minChar) {//已经加入的就不算了
                    minChar = c;
                    start = i+1; //下个start在找到的最小字母后
                    
                }
            }
            
            sb.append(minChar);
            lastIndex[minChar - 'a'] = -1; //已经加入的字母就记录成没有
            
            if (s.charAt(end) == minChar) end = getMin(lastIndex); //条件
        }
        
        return sb.toString();
        
    }
    private int getMin (int[] array) {
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < array.length; i++) {
            if (array[i] < 0) continue;
            if (array[i] < min) {
                min = array[i];
            }
        }

        return min;
    }

两种解法都是O(n),但第一个是O(26n),第二个是O(2n),第二个快

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s