Java O(n) Easy To Understand, Optimal Solution


  • 0
    B

    Explanation
    The idea to this question is to use Bucket Sort, taking advantage of the fact that the minimum and maximum frequencies a character in s can occur are 0 and s.length(), respectively.

    1. Construct a dictionary, that maps each distinct character to it's frequency in s.
    2. Create an array of lists, freqs, with size s.length()+1. The index of a list in freqs is very informative. Suppose freqs[4] = { 'a', 'b', 'c' }. This means characters a, b, c occur 4 times each in s. Populate freqs with data from the dictionary in step 1).
    3. Generate our solution using the freqs array. This step runs in O(n), since we scan through all s.length()+1 indices of freqs, and in total the number of characters to append is s.length(): O(n) + O(n) = O(n).

    Time Complexity
    The time complexity is O(n) where n is the number of characters in s, since steps 1, 2, 3 all run in O(n) time.

    class Solution {
        public String frequencySort(String s) {
            // 1. Maps character to its frequency
            Map<Character, Integer> charMap = new HashMap<>();
            for (int i = 0; i < s.length(); i++) {
                char c = s.charAt(i);
                Integer count = charMap.get(c);
                if (count == null) {
                    charMap.put(c, 1);
                } else {
                    charMap.put(c, count + 1);
                }
            }
            
            // 2. Use Bucket Sort - index indicates frequency
            ArrayList<Character> [] freqs = 
                                 new ArrayList[s.length() + 1];
            for (char c : charMap.keySet()) {
                int freq = charMap.get(c);
                if (freqs[freq] == null) {
                    freqs[freq] = new ArrayList<>();
                }
                freqs[freq].add(c);
            }
            
            // 3. Build our end-result string
            StringBuilder sb = new StringBuilder();
            for (int i = freqs.length - 1; i >= 1; i--) {
                if (freqs[i] != null) {
                    for (Character c : freqs[i]) {
                        // Append the character i amount of times
                        for (int j = 0; j < i; j++) {
                            sb.append(c);
                        }
                    }
                }
            }
            return new String(sb);
        }
    }
    

Log in to reply
 

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