Super Simple and Easy to Understand Java Solution


  • 0
    L
    public String removeDuplicateLetters(String s) {
        int[] count = new int[26];
        boolean[] visited = new boolean[26];
        int nUnique = countLetters(s, count); // return # unique letters, fill count with # of each letter
        
        char[] letters = new char[nUnique];
        char[] array = s.toCharArray();
        int j = -1; // last letter in letters
        
       for (int i = 0; i < array.length; i++) {
            count[array[i] - 'a']--; // # current letter left
            if (visited[array[i] - 'a']) continue; // letters only contains unique letters
            
            while (j >= 0 && array[i] < letters[j] && count[letters[j] - 'a'] > 0) { // regret the greedy choice
                visited[letters[j--] - 'a'] = false;
            }
            letters[++j] = array[i]; // make a greedy choice
            visited[array[i] - 'a'] = true;
        }
        
        return String.valueOf(letters);
    }

Log in to reply
 

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