[451. Sort Characters By Frequency] #leetcode

451_0927.java

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);
            }
        }
        
        // concrete style 
        // PriorityQueue<Map.Entry<Character, Integer>> pq = new PriorityQueue<>(
        //     (a, b) -> b.getValue() - a.getValue()
        // );
      
        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();
    }
}


class Solution {
  // O(n) O(n)
    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 c : map.keySet()) {
            int count = map.get(c);
            if (bucket[count] == null) {
                bucket[count] = new ArrayList<Character>();
            }
            bucket[count].add(c);
        }
        
        StringBuilder sb = new StringBuilder();
        for (int i = s.length(); i > 0; i--) {
            if (bucket[i] != null) {
                for (char c : bucket[i]) {
                    for (int j = 0; j < i; j++) {
                        sb.append(c);
                    }
                }    
            } 
        }
        
        return sb.toString();
    }
}