316. Remove Duplicate Letters

Link

Given a string which contains only lowercase letters, remove duplicate letters so that every letter appears 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"

Note: This question is the same as 1081: https://leetcode.com/problems/smallest-subsequence-of-distinct-characters/

Solution

TimeComplexity : O(n)

 public String removeDuplicateLetters(String s) {
        int[] count = new int[26];
        boolean[] isInsided = new boolean[26];
        
        for(int i = 0; i < 26; i++){
            isInsided[i] = false;
        }
        
        for(int i = 0; i < s.length(); i++){
            count[s.charAt(i) - 'a']++;
        }
        
        StringBuilder sb = new StringBuilder();
        Stack<Character> stack = new Stack<>();
        for(int i = 0; i < s.length(); i++){
            char cur = s.charAt(i);
            count[cur - 'a']--;
            
            if(isInsided[cur - 'a']){
                continue;
            }
            //當要放入的字母比之前的字母小，且之前的字母後面還有，那就先pop出之前的字母
            while(!stack.isEmpty() && stack.peek() > cur && count[stack.peek()-'a'] > 0){
                isInsided[stack.peek() - 'a'] = false;
                stack.pop();
            }
            stack.push(cur);
            isInsided[cur - 'a'] = true;
            
        }
        while(!stack.isEmpty()){
            sb.insert(0, stack.pop());
        }
        
        return sb.toString();
    }