Java O(n) Bucket Sort Solution / O(nlogn) PriorityQueue Solution, easy to understand


  • 33
    R

    The logic is very similar to NO.347 and here we just use a map a count and according to the frequency to put it into the right bucket. Then we go through the bucket to get the most frequently character and append that to the final stringbuilder.

    public class Solution {
        public String frequencySort(String s) {
            Map<Character, Integer> map = new HashMap<>();
            for (char c : s.toCharArray()) {
                if (map.containsKey(c)) {
                    map.put(c, map.get(c) + 1);
                } else {
                    map.put(c, 1);
                }
            }
            List<Character> [] bucket = new List[s.length() + 1];
            for (char key : map.keySet()) {
                int frequency = map.get(key);
                if (bucket[frequency] == null) {
                    bucket[frequency] = new ArrayList<>();
                }
                bucket[frequency].add(key);
            }
            StringBuilder sb = new StringBuilder();
            for (int pos = bucket.length - 1; pos >=0; pos--) {
                if (bucket[pos] != null) {
                    for (char num : bucket[pos]) {
                        for (int i = 0; i < map.get(num); i++) {
                            sb.append(num);
                        }
                    }
                }
            }
            return sb.toString();
        }
    }
    
    

    And we have normal way using PriorityQueue as follows:

    public class Solution {
        public String frequencySort(String s) {
            Map<Character, Integer> map = new HashMap<>();
            for (char c : s.toCharArray()) {
                if (map.containsKey(c)) {
                    map.put(c, map.get(c) + 1);
                } else {
                    map.put(c, 1);
                }
            }
            PriorityQueue<Map.Entry<Character, Integer>> pq = new PriorityQueue<>(
                new Comparator<Map.Entry<Character, Integer>>() {
                    @Override
                    public int compare(Map.Entry<Character, Integer> a, Map.Entry<Character, Integer> b) {
                        return b.getValue() - a.getValue();
                    }
                }
            );
            pq.addAll(map.entrySet());
            StringBuilder sb = new StringBuilder();
            while (!pq.isEmpty()) {
                Map.Entry e = pq.poll();
                for (int i = 0; i < (int)e.getValue(); i++) {
                    sb.append(e.getKey());
                }
            }
            return sb.toString();
        }
    }
    

  • 0
    S
    This post is deleted!

  • 0
    L

    Nice bucket sort solution!


  • 2

    Why is the PQ solution's run time if O(nlogn) but not O(n)? After all you can only can constant number of chars.


  • 5
    F

    Actually, the last loop

     for (int i = 0; i < map.get(num); i++) {
           sb.append(num);
     }
    

    can be changed with

     for (int i = 0; i < pos; i++) {
           sb.append(num);
     }
    

    Since each char's frequency are the position in the bucket[];


  • 3
    Z

    Hi,

    I have a question related to the complexity. That is since the set of character must be in a constant space whose size is either 128 or 256 or... Will we still treat the complexity of insertion into the heap as O(logn)? Or should we treat it as constant?


  • 0
    E

    @DonaldTrump IMHO it's because poll() itself is O(nlogn) and even tho we only have a limited number of entries in the PriorityQueue, the number isn't input independent


  • 0
    B

    You can add a max to save the space.

    public class Solution {
        public String frequencySort(String s) {
            Map<Character, Integer> map = new HashMap<>();
            int max = 0;
            for (char c : s.toCharArray()) {
                if (map.containsKey(c)) {
                    map.put(c, map.get(c) + 1);
                } else {
                    map.put(c, 1);
                }
                max = Math.max(max, map.get(c));
            }
            List<Character> [] bucket = new List[max + 1];
            for (char key : map.keySet()) {
                int frequency = map.get(key);
                if (bucket[frequency] == null) {
                    bucket[frequency] = new ArrayList<>();
                }
                bucket[frequency].add(key);
            }
            StringBuilder sb = new StringBuilder();
            for (int pos = bucket.length - 1; pos >=0; pos--) {
                if (bucket[pos] != null) {
                    for (char num : bucket[pos]) {
                        for (int i = 0; i < map.get(num); i++) {
                            sb.append(num);
                        }
                    }
                }
            }
            return sb.toString();
        }
    }

  • 0
    J

    The PriorityQueue Method is O(n) as well because you have only constant number (at most 52) of Map.Entry to maintain. The bottleneck is the first for loop which is O(n).


  • 0
    A

    Useful solution. Thank you.
    Maybe we can save a little bit of memory by using a freq array of size 128 instead of a map and pairing it up with a bitset to account for duplicate characters.

    public String frequencySort(String s) {
            if(s==null || s.length()<3) return s;
            int[] arr1 = new int[128];
            for(int i=0; i<s.length(); i++) {
                char c = s.charAt(i);
                arr1[c]++;
            }
            List<Character>[] arr2 = new List[s.length()+1];
            BitSet b = new BitSet(128);
            for(int i=0; i<s.length(); i++) {
                char c = s.charAt(i);
                if(b.get(c)) continue;
                b.set(c);
                int idx = arr1[c];
                if(arr2[idx]==null) {
                    arr2[idx] = new ArrayList<> ();
                }
                arr2[idx].add(c);
            }
            StringBuilder sb = new StringBuilder();
            for(int i=arr2.length-1; i>=0; i--) {
                if(arr2[i]!=null) {
                    for(char c : arr2[i])
                        for(int j=0; j<i; j++)
                            sb.append(c);
                }
            }
            return sb.toString();
        }
    

  • 0
    N

    what if when the frequency is the same, then order by the alphabetic order.

    for example input: acaacbb output: aaabbcc

    How to achieve that?


  • 0
    W

    Anyone can tell me why I got the LTE? Thx

    public String frequencySort(String s) {  
       if(s == null || s.length() <= 1)
            return s;
        
        Map<Character, String> map = new HashMap<>();
        for(char c: s.toCharArray()){
            map.put(c, map.getOrDefault(c, "") + c);
        }
        
        PriorityQueue<Map.Entry<Character, String>> pq = new PriorityQueue<>(
            new Comparator<Map.Entry<Character, String>>() {
                @Override
                public int compare(Map.Entry<Character, String> a, Map.Entry<Character, String> b) {
                    return b.getValue().length() - a.getValue().length();
                }
            }
        );
        pq.addAll(map.entrySet());
        
        StringBuilder sb = new StringBuilder();
        while(!pq.isEmpty()){
            sb.append(pq.poll().getValue());
        }
        
        return sb.toString();
    }

  • 3
    B

    @WhyTalent
    FYI

    I also use HashMap + PriorityQueue but with a more concise data structure like you.

    However, my solution got TLE first. After changing all the String to StringBuilder, I got accepted! It's quite interesting in the performance gap between += in String and append() in StringBuilder.

    public class Solution {
        public String frequencySort(String s) {
            Map<Character, StringBuilder> map = new HashMap<>();
            for (int i = 0; i < s.length(); i++) {
                char c = s.charAt(i);
                map.put(c, map.getOrDefault(c, new StringBuilder()).append(c));
            }
            
            PriorityQueue<StringBuilder> queue = new PriorityQueue<>((a, b) -> (b.length() - a.length()));
            queue.addAll(map.values());
            
            StringBuilder sb = new StringBuilder();
            while (!queue.isEmpty()) {
                sb.append(queue.poll());
            }
            return sb.toString();
        }
    }
    

  • 0
    W

    @bun919tw Yeah, you're right. thx


  • 0

    A bit of Java 8.

    public String frequencySort(String s) {
        Map<Character, Integer> map = new HashMap<>();
    
        IntStream.range(0, s.length()).forEach(i -> map.put(s.charAt(i), map.getOrDefault(s.charAt(i), 0) + 1));
        
        PriorityQueue<Map.Entry<Character, Integer>> pq = new PriorityQueue<>((a, b) -> b.getValue() - a.getValue());
        
        pq.addAll(map.entrySet());
    
        StringBuilder sb = new StringBuilder();
        while (!pq.isEmpty()) {
            Map.Entry e = pq.poll();
            IntStream.range(0, (int) e.getValue()).forEach(i -> sb.append(e.getKey()));
        }
        return sb.toString();
    }

Log in to reply
 

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