Sort string in decreasing order based on character frequency.
Input: s="tree" → Output: "eert"
Input: s="cccaaa" → Output: "cccaaa"
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
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)