[Java] O(n) time, O(1) space, different intuition, no letter count, no stack, no visited array


  • 0
    F

    My solution only maps the letter to the index where it last appeared. The intuition is that we must pick a letter within the range where all letters are before its last index, and we pick the minimum one within this range. (This is same theory as the letter count approach because if we reach the last index of a letter then its count must has been decreased to 0.) The reason is that we must pick one instance of the current letter between current index and its last index, if there are other smaller letter choose the smaller first, otherwise pick the current letter at the current index.

    For example, "cbabc", when checking 'c', last index of 'c' is 4, so we must pick a letter between 0 - 3. When checking 'b', we see b's last index is 3, so the range reduces to 0 - 2. When checking 'a', 'a' is the smallest in range 0 - 2 and we reached the end of the range. So 'a' is appended to result, 'a' is cleared out from the map, the iteration continues after 'a'.

    The runtime looks like O(n^2), but like others have argued, it's at most 26*n because the if(map[s.charAt(start)] > -1){ ... } will be ran at most 26 times.

    public class Solution {
        public String removeDuplicateLetters(String s) {
            int[] map = new int[128];
            Arrays.fill(map, -1);
            for(int i = 0; i < s.length(); i++){
                map[s.charAt(i)] = i;
            }
            
            StringBuilder sb = new StringBuilder();
            for(int start = 0; start < s.length(); start++){
                if(map[s.charAt(start)] > -1){
                    int end = map[s.charAt(start)];
                    int minIndex = start;
                    for(int i = start+1; i < end; i++){
                        if(map[s.charAt(i)] > -1){
                            end = Math.min(end, map[s.charAt(i)]);
                            if(s.charAt(i) < s.charAt(minIndex))
                                minIndex = i;
                        }
                    }
                    sb.append(s.charAt(minIndex));
                    map[s.charAt(minIndex)] = -1;
                    start = minIndex;
                }
            }
            return sb.toString();
        }
    }
    

Log in to reply
 

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