Java O(n) solution, easy understand


  • 1
    H
    public String removeDuplicateLetters(String s) {
        int[] counts = new int[26];
        boolean[] added = new boolean[26];
        if(s == null) return "";
        
        for(int i=0; i<s.length(); i++) counts[s.charAt(i) -'a']++;
        
        Stack<Character> stack = new Stack<Character>();
        for(int i=0; i<s.length(); i++) {
            char c = s.charAt(i);
            int ind = c-'a';
            
            if(stack.isEmpty()) {
                stack.push(c);
                added[ind] = true;
            } else if(!added[ind]) {
                while(!stack.isEmpty() && stack.peek() > c && counts[stack.peek()-'a'] > 0) {
                    char cur = stack.pop();
                    added[cur-'a'] = false;
                }
                stack.push(c);
                added[ind] = true;
            } 
    
            counts[ind]--;
        }
        
        
        StringBuffer str = new StringBuffer();
        while(!stack.isEmpty()) str.insert(0, stack.pop());//str.insert(0, s1.pop());
        
        return str.toString();    
    }

Log in to reply
 

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