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"

分析

方法一

这道题可以采用Greedy的思想，因为最后想要的结果是最小值，所以我们在满足要求的情况下把不断append最小的字符, 最后便可得到最小的字符串.

关键点就是要满足什么要求以及怎么样去满足。首先要求就是得保证在原来的字符串中存在当前字符append的顺序，即要保证每次append的字符的次数大于0。我们可以用一个数组记录每个字符出现的次数，用一个指针从左到右扫，过程中减小对应字符次数，找当前最小字符, 找的过程中终止条件是发现某个字符次数等于0，因为继续扫的话最终结果很有可能缺那个字符.

方法二

其实跟上个方法差不多，但是可以优化下，用stack的话，最多每个字符过两遍就可以了。读字符的过程中，把字符存到stack里，当发现stack之前存的字符中比当前字符大而且频率还大于0就可以把那个字符pop出去。类似这种题目都可以用stack解决。基本思想就是在一定的限制条件下pop出比当前选择差的元素。

复杂度

方法一

time: O(kn), space: O(k), k表示原字符串中unique字符的个数

方法二

time: O(n), space: O(k)

代码

方法一

public class Solution {
    public String removeDuplicateLetters(String s) {
        if (s == null ||s.length() == 0)
            return 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;
        }
        
        // 除去字符串中已经append的字符的所有重复值
        return s.charAt(pos) + removeDuplicateLetters(s.substring(pos + 1).replaceAll("" + s.charAt(pos), ""));
    }
}

方法二

public class Solution {
    public String removeDuplicateLetters(String s) {
        int[] freqs = new int[256];
        
        // 统计字符频率
        for (int i = 0; i < s.length(); i++) {
            freqs[s.charAt(i)]++;
        }

        boolean[] visited = new boolean[256]; // 用来标记存在stack里的字符
        Deque<Character> q = new ArrayDeque<>();    
        
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            freqs[c]--;
            if (visited[c]) continue;

            // pop出stack当中比当前字符大但后面还存在的的字符，
            while (!q.isEmpty() && q.peek() > c && freqs[q.peek()] > 0) {
                visited[q.pop()] = false;
            }
            q.push(c);
            visited[c] = true;
        }

        StringBuilder sb = new StringBuilder();
        for (char c : q) {
            sb.append(c);
        }

        return sb.reverse().toString();
    }
}