Code Logo

Sort Characters By Frequency

Published at23 Jul 2026
Created by
Medium 0 views
Like0

Given a string s, sort it in decreasing order based on the frequency of characters. Return the sorted string. If multiple characters have the same frequency, any order is acceptable.

A hash map counts character frequencies. Then sort characters by their frequency in descending order. Build the result by repeating each character by its frequency.

For example, s = "tree" has t:1, r:1, e:2, so the output is "eert" or "eetr".

Alternative approaches include using a bucket sort (O(n)) instead of comparison sort (O(n log n)). Since the maximum frequency is bounded by the string length, creating an array of buckets indexed by frequency and then iterating from highest to lowest produces a sorted result in O(n) time.

The bucket sort approach runs in O(n) time by creating an array of buckets indexed by frequency. Characters are placed into buckets, then iterated from highest frequency to lowest. This is faster than comparison-based sorting when n is large.

The bucket sort approach uses an array where the index represents the frequency. Characters with the same frequency are stored in the same bucket. By iterating from the highest index downward, we output characters in decreasing frequency order without needing a comparison sort. This runs in O(n) time.

Example Input & Output

Example 1
Input
"cccaaa"
Output
"aaaccc" or "cccaaa"
Explanation

Both appear 3 times.

Example 2
Input
"tree"
Output
"eert" or "eetr"
Explanation

e appears twice, t and r once.

Example 3
Input
"Aabb"
Output
"bbAa" or "bbaA"
Explanation

Case sensitive: b:2, a:1, A:1.

Algorithm Flow

Recommendation Algorithm Flow for Sort Characters By Frequency
Recommendation Algorithm Flow for Sort Characters By Frequency

Solution Approach

Count frequencies. Sort characters by frequency descending. Build result string.

function solution(s) {
  var freq = {};
  for (var i = 0; i < s.length; i++) freq[s[i]] = (freq[s[i]] || 0) + 1;
  var chars = Object.keys(freq).sort(function(a, b) { return freq[b] - freq[a]; });
  var result = '';
  for (var i = 0; i < chars.length; i++) result += chars[i].repeat(freq[chars[i]]);
  return result;
}

Time O(n log n), Space O(n).

Best Answers

java
import java.util.*;
class Solution {
    public String solution(String s) {
        Map<Character,Integer> freq = new HashMap<>();
        for (char ch : s.toCharArray()) freq.put(ch, freq.getOrDefault(ch, 0) + 1);
        List<Character> chars = new ArrayList<>(freq.keySet());
        chars.sort((a,b) -> freq.get(b) - freq.get(a));
        StringBuilder sb = new StringBuilder();
        for (char ch : chars) {
            for (int i = 0; i < freq.get(ch); i++) sb.append(ch);
        }
        return sb.toString();
    }
}