Using stack


  • 0
    T
    public String removeDuplicateLetters(String s) {
        if (s.length() == 0) {
            return "";
        }
        int[] count = new int[26];
        boolean[] visited = new boolean[26];
        Stack<Character> stack = new Stack<Character>();
        StringBuilder res = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            count[s.charAt(i) - 'a']++;
        }
        
        for (int i = 0; i < s.length(); i++) {
            count[s.charAt(i) - 'a']--;
            if (visited[s.charAt(i) - 'a']) {
                continue;
            }
            while (!stack.isEmpty() && s.charAt(i) < stack.peek() && count[stack.peek() - 'a'] > 0) {
                char c = stack.pop();
                visited[c - 'a'] = false;
            }
            stack.push(s.charAt(i));
            visited[s.charAt(i) - 'a'] = true;
        }
        
        while (!stack.isEmpty()) {
            res.insert(0, stack.pop());
        }
        return res.toString();
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.