Beat 99%, 18 lines code, O(n) time, Greedy + DP solution with explanation


  • 0
    F
    // let A[i] is for the result of removeDuplicatedLetters for s.substring(0,i+1);
    // initially, A[0] = s.substring(0,1);
    // transition function:
    // A[i+1] is following:
    // if s.charAt(i) has existed in A[i], A[i+1] = A[i];
    // otherwise: go through from A[i] back to front, find the pos which store either the element whose count is 0 or the element in A[i] which is less than s.charAt(i), add s.charAt(i) into pos+1, let A[i+1] end pos is pos+2;
    
    public String removeDuplicateLetters(String s) {
            if (s.length() < 2) return s;
            int[] counter = new int[26];
            boolean[] visited = new boolean[26];
            char[] array = new char[27];
            int arrayPos = 0;
            
            char[] cs = s.toCharArray();
            for (int i = 0; i < cs.length; i++) counter[cs[i]-'a']++;
            for (int i = 0; i < cs.length; i++) {
                int index = cs[i]-'a';
                counter[index]--;
                if (visited[index]) continue;
                while (arrayPos > 0 && counter[array[arrayPos-1]-'a'] > 0 && array[arrayPos-1] > cs[i]) 
                visited[array[--arrayPos]-'a'] = false;
                array[arrayPos++] = cs[i]; 
                visited[index] = true;
            }
            
            return new String(array, 0, arrayPos);
        }

Log in to reply
 

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