[LeetCode 316] Remove Duplicate

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:

Input: "bcabc"
Output: "abc"

Example 2:

Input: "cbacdcbc"
Output: "acdb"

Solution： HashTable + Visited[]

1. 难点在于需要找到smallest in lexicographical order的结果。 不能只根据 hashtable的频次来remove，否则无法找到最小字典序。
2. 两个数据结构： Frequency HashTable,和 boolean[] visited
3. 首先求得 Frequency HashTable
4. 再遍历每个字符
   • 更新Frequency HashTable （必须先更新，否则遇到bbaac, 处理到A的时候就会把结果集中的bremove掉，最终结果错误）
   • 如果当前字符已经visited，则说明已经在结果集中，无需再处理，continue。
   • 把当前字符加入结果集。
   • However， 如果当前字符的字典序比结果集中最后一位小，且结果集中最后一位的frequency > 0. 说明最后一位在后面还会出现，所以它不应该出现在当前字符的前面，需要从结果集中remove掉。更新visited[].

while (result.length () > 0 && ch < result.charAt (result.length () - 1) && frequency[result.charAt (result.length () - 1) - 'a'] > 0) {
               // System.out.println (result.charAt (result.length () - 1));
                visited[result.charAt (result.length () - 1) - 'a'] = false;
                result.deleteCharAt (result.length () - 1);
            }

• 更新当前字符的visited[], 然后将其加入结果集。

Code

class Solution {
    public String removeDuplicateLetters(String s) {
        if (s == null || s.length () == 0)
            return s;
        
        int[] frequency = new int[26];
        boolean[] visited = new boolean[26];
        StringBuilder result = new StringBuilder ();
        
        for (char ch : s.toCharArray ()) {
            int index = ch - 'a';
            frequency [index] ++;
        }
        
        for (char ch : s.toCharArray ()) {
            int index = ch - 'a';
            frequency [index] --;
            
            if (visited[index])
                continue;
            
            while (result.length () > 0 && ch < result.charAt (result.length () - 1) && frequency[result.charAt (result.length () - 1) - 'a'] > 0) {
               // System.out.println (result.charAt (result.length () - 1));
                visited[result.charAt (result.length () - 1) - 'a'] = false;
                result.deleteCharAt (result.length () - 1);
            }
            
            visited[index] = true;
            result.append (ch);  
        }
        
        return result.toString ();
    }
}