Sort Characters By Frequency

Share

Sort string in decreasing order based on character frequency.

Example 1
Input: s="tree" → Output: "eert"
Example 2
Input: s="cccaaa" → Output: "cccaaa"

Solution Approach

Count frequencies, use max-heap to build result from most to least frequent.

  • Count character frequencies
  • Add all (freq, char) to max-heap
  • Poll and append each char freq times
  • Return result string
Java
public String frequencySort(String s) {
    Map<Character, Integer> freq = new HashMap<>();
    for (char c : s.toCharArray()) freq.merge(c, 1, Integer::sum);
    PriorityQueue<Map.Entry<Character,Integer>> pq = new PriorityQueue<>((a,b)->b.getValue()-a.getValue());
    pq.addAll(freq.entrySet());
    StringBuilder sb = new StringBuilder();
    while (!pq.isEmpty()) {
        Map.Entry<Character,Integer> e = pq.poll();
        sb.append(String.valueOf(e.getKey()).repeat(e.getValue()));
    }
    return sb.toString();
}
  • Time Complexity: O(n log n)
  • Space Complexity: O(n)