Tuesday, October 11, 2016

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"

The idea is to use a stack. Go through the string twice. First count the occurrence of each letters. In the second time, if there are existing chars in stack that are larger than current one, and we know later the same letter will appear again, we pop the letter from the stack. We then add current letter when no more letters can be popped out.




 public String removeDuplicateLetters(String s) {
        if (s.length() <= 1) {
            return s;
        }
        
        Stack chars = new Stack<>();
        int[] counter = new int[26];
        boolean[] visited = new boolean[26];
        
        for (int i = 0; i < s.length(); i++) {
            counter[s.charAt(i) - 'a']++;
        }
        
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            counter[c - 'a']--;
            if (visited[c - 'a']) {
                continue;
            }
            while (!chars.isEmpty() && chars.peek() > c && counter[chars.peek() - 'a'] > 0) {
                visited[chars.pop() - 'a'] = false;
            }
            chars.push(c);
            visited[c - 'a'] = true;
        }
        StringBuilder builder = new StringBuilder();
        while (!chars.isEmpty()) {
            builder.append(chars.pop());
        }
        return builder.reverse().toString();
    }


No comments:

Post a Comment