7 ms simple Java solution (34 ms if you use Sets/Maps)


  • 0
    M

    34 ms version (easier to understand):

    import java.util.HashMap;
    import java.util.Map;
    import java.util.Set;
    import java.util.TreeSet;
    
    public class Solution34ms {
        public String removeDuplicateLetters(String s) {
            if ((s == null) || (s.length() < 2))
                return s;
    
            // For each char, find the index of its last occurrence:
            final Map<Character, Integer> lastPositions = new HashMap<>();
            for (int i = 0; i < s.length(); ++i) {
                lastPositions.put(s.charAt(i), i);
            }
    
            // Sort chars by index of last occurrence:
            final Set<Integer> sortedLastPositions = new TreeSet<>(lastPositions.values());
    
            // Smallest lexicographical sub-sequence:
            final StringBuilder result = new StringBuilder();
    
            int low = 0;
            while (!sortedLastPositions.isEmpty()) {
                final int high = sortedLastPositions.iterator().next();
    
                while (low <= high) {
                    // Find minimum character to add:
                    char minChar = Character.MAX_VALUE;
                    for (int i = low; i <= high; ++i) {
                        final char c = s.charAt(i);
                        if ((c < minChar) && lastPositions.containsKey(c)) {
                            low = i + 1;
                            minChar = c;
                        }
                    }
    
                    result.append(minChar);
                    sortedLastPositions.remove(lastPositions.remove(minChar));
                    if ((sortedLastPositions.isEmpty()) || (minChar == s.charAt(high)))
                        break;
                }
                sortedLastPositions.remove(high);
            }
            return result.toString();
        }
    }
    

    ... and an optimized 7 ms version, using simple arrays and assuming only a-z as the alphabet:

    import java.util.Arrays;
    
    public class Solution7ms {
        private static final int NUM_CHARS = 26;
    
        public String removeDuplicateLetters(String s) {
            if ((s == null) || (s.length() < 2))
                return s;
    
            // For each char, find the index of its last occurrence:
            final boolean[] visited = new boolean[NUM_CHARS];
            final int[] lastPositions = new int[NUM_CHARS];
            Arrays.fill(lastPositions, Integer.MAX_VALUE);
            for (int i = 0; i < s.length(); ++i) {
                final char c = s.charAt(i);
                final int index = c - 'a';
                lastPositions[index] = i;
                visited[index] = true;
            }
    
            Arrays.sort(lastPositions);
    
            // Smallest lexicographical sub-sequence:
            final StringBuilder result = new StringBuilder();
    
            int low = 0;
            int k = 0;
            int high = lastPositions[k];
            while (high != Integer.MAX_VALUE) {
                boolean early = false;
                while (low <= high) {
                    // Find minimum character to add:
                    char minChar = Character.MAX_VALUE;
                    for (int i = low; i <= high; ++i) {
                        final char c = s.charAt(i);
                        if ((c < minChar) && visited[c - 'a']) {
                            low = i + 1;
                            minChar = c;
                        }
                    }
    
                    result.append(minChar);
                    visited[minChar - 'a'] = false;
                    if (minChar == s.charAt(high))
                        break;
                }
    
                // Move to next "upper-bound" character:
                while ((k < NUM_CHARS) && (lastPositions[k] != Integer.MAX_VALUE) && !visited[s.charAt(lastPositions[k]) - 'a'])
                    ++k;
                if (k >= NUM_CHARS)
                    break;
                high = lastPositions[k];
            }
            return result.toString();
        }
    }

Log in to reply
 

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