Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Sort Characters By Frequency

MEDIUMProblemSolveExternal Links

Description

Given a string s, sort it in decreasing order based on the frequency of the characters. The frequency of a character is the number of times it appears in the string.

Return the sorted string. If there are multiple answers, return any of them.

Examples

Example 1

Input: s = "tree"

Output: "eert"

Explanation: 'e' appears twice, while 't' and 'r' each appear once. So 'e' must appear before both 't' and 'r'. "eetr" is also a valid answer.

Example 2

Input: s = "cccaaa"

Output: "aaaccc"

Explanation: Both 'a' and 'c' appear three times. So both "aaaccc" and "cccaaa" are valid answers. Note that "cacaca" is incorrect, as the same characters must be grouped together.

Example 3

Input: s = "Aabb"

Output: "bbAa"

Explanation: 'b' appears twice, while 'A' and 'a' each appear once. Note that 'A' and 'a' are treated as two different characters (case-sensitive). "bbaA" is also a valid answer.

Constraints

  • 1 ≤ s.length ≤ 5 × 10⁵
  • s consists of uppercase and lowercase English letters and digits

Editorial

Brute Force

Intuition

The most straightforward approach is to repeatedly find the character with the highest remaining frequency and append all its occurrences to the result.

Imagine you have a pile of letters. To build the answer, you look through the entire pile to find which letter appears the most. You pick out all copies of that letter and place them at the start of your result. Then you look through the pile again for the next most frequent letter, and so on, until the pile is empty.

This uses nested loops: an outer loop that runs until all characters are placed, and an inner loop that scans the string each time to count characters. It works correctly but does redundant counting work.

Step-by-Step Explanation

Let's trace through with s = "tree":

Step 1: Create a boolean array used of size n to track which characters have already been placed in the result. Result = "".

Step 2 — Round 1: Scan the entire string to find the character with the highest frequency among unused characters.

  • Count frequencies: 't' → 1, 'r' → 1, 'e' → 2
  • 'e' has the highest frequency (2)
  • Append all 'e's to result: result = "ee"
  • Mark all 'e' positions as used: used = [false, false, true, true]

Step 3 — Round 2: Scan again for the next highest-frequency unused character.

  • Remaining: 't' → 1, 'r' → 1 (tied)
  • Pick 't' (or 'r', order among ties doesn't matter)
  • Append: result = "eet"
  • Mark 't' as used: used = [true, false, true, true]

Step 4 — Round 3: Scan again.

  • Remaining: 'r' → 1
  • Append: result = "eetr"
  • Mark 'r' as used: used = [true, true, true, true]

Step 5: All characters used. Return "eetr".

Algorithm

  1. Create a boolean array used of size n, initialized to false
  2. Initialize an empty result string
  3. While the result length < n:
    a. Scan the string and count frequency of each unused character
    b. Find the character with the maximum frequency
    c. Append that character frequency times to the result
    d. Mark all occurrences of that character as used
  4. Return the result

Code

class Solution {
public:
    string frequencySort(string s) {
        int n = s.size();
        vector<bool> used(n, false);
        string result = "";
        
        while ((int)result.size() < n) {
            // Count frequency of each unused character
            unordered_map<char, int> freq;
            for (int i = 0; i < n; i++) {
                if (!used[i]) {
                    freq[s[i]]++;
                }
            }
            
            // Find character with max frequency
            char maxChar = 0;
            int maxFreq = 0;
            for (auto& [ch, f] : freq) {
                if (f > maxFreq) {
                    maxFreq = f;
                    maxChar = ch;
                }
            }
            
            // Append all occurrences and mark as used
            for (int i = 0; i < n; i++) {
                if (!used[i] && s[i] == maxChar) {
                    result += maxChar;
                    used[i] = true;
                }
            }
        }
        
        return result;
    }
};
class Solution:
    def frequencySort(self, s: str) -> str:
        n = len(s)
        used = [False] * n
        result = []
        
        while len(result) < n:
            # Count frequency of each unused character
            freq = {}
            for i in range(n):
                if not used[i]:
                    freq[s[i]] = freq.get(s[i], 0) + 1
            
            # Find character with max frequency
            max_char = max(freq, key=freq.get)
            
            # Append all occurrences and mark used
            for i in range(n):
                if not used[i] and s[i] == max_char:
                    result.append(max_char)
                    used[i] = True
        
        return ''.join(result)
import java.util.HashMap;
import java.util.Map;

class Solution {
    public String frequencySort(String s) {
        int n = s.length();
        boolean[] used = new boolean[n];
        StringBuilder result = new StringBuilder();
        
        while (result.length() < n) {
            // Count frequency of each unused character
            Map<Character, Integer> freq = new HashMap<>();
            for (int i = 0; i < n; i++) {
                if (!used[i]) {
                    freq.merge(s.charAt(i), 1, Integer::sum);
                }
            }
            
            // Find character with max frequency
            char maxChar = 0;
            int maxFreq = 0;
            for (Map.Entry<Character, Integer> entry : freq.entrySet()) {
                if (entry.getValue() > maxFreq) {
                    maxFreq = entry.getValue();
                    maxChar = entry.getKey();
                }
            }
            
            // Append all occurrences and mark used
            for (int i = 0; i < n; i++) {
                if (!used[i] && s.charAt(i) == maxChar) {
                    result.append(maxChar);
                    used[i] = true;
                }
            }
        }
        
        return result.toString();
    }
}

Complexity Analysis

Time Complexity: O(k × n)

Where k is the number of unique characters and n is the string length. We perform k rounds (one per unique character), and each round scans the entire string O(n). In the worst case where every character is unique, k = n and this becomes O(n²).

Space Complexity: O(n)

The used array takes O(n) space, and the frequency map takes O(k) space per round. The result string takes O(n).

Why This Approach Is Not Efficient

The brute force re-counts character frequencies in every round. If there are k unique characters, we scan the string k times, leading to O(k × n) time, which degrades to O(n²) when most characters are unique.

The key waste is that frequency counting is repeated work. If we count all frequencies just once upfront and store them in a hash map, we eliminate all the redundant scans. Then we just need to sort the unique characters by their frequency and build the result — which is exactly what the next approach does.

Better Approach - HashMap + Sorting

Intuition

Instead of repeatedly scanning the string, count all character frequencies once using a hash map. Then collect the unique characters and sort them by frequency in descending order. Finally, build the result by repeating each character according to its count.

Think of it like a teacher counting how many students chose each favourite colour. Rather than re-counting each time they want the next popular colour, they count once, write all counts on a list, sort the list from most to least popular, and read it off.

Step-by-Step Explanation

Let's trace through with s = "tree":

Step 1: Build frequency map by scanning the string once:

  • s[0] = 't' → freq = {'t': 1}
  • s[1] = 'r' → freq = {'t': 1, 'r': 1}
  • s[2] = 'e' → freq = {'t': 1, 'r': 1, 'e': 1}
  • s[3] = 'e' → freq = {'t': 1, 'r': 1, 'e': 2}

Step 2: Collect unique characters with their frequencies as pairs: [('t', 1), ('r', 1), ('e', 2)].

Step 3: Sort by frequency descending: [('e', 2), ('t', 1), ('r', 1)].

Step 4: Build result by repeating each character:

  • 'e' × 2 → "ee"
  • 't' × 1 → "eet"
  • 'r' × 1 → "eetr"

Result: "eetr".

Build Frequency Map, Then Sort — O(n + k log k) — First we count every character's frequency in a single pass, then sort unique characters by count, and finally build the output string.

Algorithm

  1. Build a frequency map: scan the string once, counting occurrences of each character
  2. Collect all unique characters into a list of (character, frequency) pairs
  3. Sort the list by frequency in descending order
  4. Build the result string by appending each character repeated by its frequency
  5. Return the result

Code

#include <string>
#include <unordered_map>
#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    string frequencySort(string s) {
        // Step 1: Count frequencies
        unordered_map<char, int> freq;
        for (char c : s) {
            freq[c]++;
        }
        
        // Step 2: Collect and sort by frequency descending
        vector<pair<char, int>> chars(freq.begin(), freq.end());
        sort(chars.begin(), chars.end(), [](const pair<char,int>& a, const pair<char,int>& b) {
            return a.second > b.second;
        });
        
        // Step 3: Build result
        string result = "";
        for (auto& [ch, count] : chars) {
            result += string(count, ch);
        }
        
        return result;
    }
};
from collections import Counter

class Solution:
    def frequencySort(self, s: str) -> str:
        # Step 1: Count frequencies
        freq = Counter(s)
        
        # Step 2: Sort by frequency descending
        sorted_chars = sorted(freq.keys(), key=lambda c: freq[c], reverse=True)
        
        # Step 3: Build result
        result = []
        for ch in sorted_chars:
            result.append(ch * freq[ch])
        
        return ''.join(result)
import java.util.*;

class Solution {
    public String frequencySort(String s) {
        // Step 1: Count frequencies
        Map<Character, Integer> freq = new HashMap<>();
        for (char c : s.toCharArray()) {
            freq.merge(c, 1, Integer::sum);
        }
        
        // Step 2: Sort characters by frequency descending
        List<Character> chars = new ArrayList<>(freq.keySet());
        chars.sort((a, b) -> freq.get(b) - freq.get(a));
        
        // Step 3: Build result
        StringBuilder result = new StringBuilder();
        for (char ch : chars) {
            for (int i = 0; i < freq.get(ch); i++) {
                result.append(ch);
            }
        }
        
        return result.toString();
    }
}

Complexity Analysis

Time Complexity: O(n + k log k)

Counting frequencies takes O(n) with one pass through the string. Sorting k unique characters takes O(k log k). Building the result takes O(n). Total: O(n + k log k). Since k ≤ 62 (26 lowercase + 26 uppercase + 10 digits), the sorting term is effectively O(1), making the practical time O(n).

Space Complexity: O(n + k)

The frequency map takes O(k) space. The result string takes O(n) space. Since k is bounded by the character set size (62), the dominant space term is O(n).

Why This Approach Is Not Efficient

While the HashMap + Sorting approach is already fast in practice (since k ≤ 62 makes sorting nearly constant time), there's a theoretical improvement possible.

The sorting step costs O(k log k). Can we avoid sorting entirely? Yes — by using Bucket Sort. Instead of sorting characters by frequency, we place each character directly into a "bucket" indexed by its frequency. Since the maximum frequency is at most n, we create an array of n+1 buckets. Each bucket holds the characters that appeared that many times. We then simply iterate from the highest bucket down to 1, collecting characters.

This replaces O(k log k) sorting with O(n) bucket placement and traversal, making the entire algorithm O(n) in both time and space.

Optimal Approach - Bucket Sort

Intuition

The key insight is that frequencies range from 1 to n (the length of the string). Instead of sorting characters by frequency, we can use the frequency as a direct index into a bucket array.

Imagine you have n+1 numbered shelves (shelf 0, shelf 1, … shelf n). After counting how often each character appears, you place each character on the shelf matching its count. 'e' appears 2 times? Put it on shelf 2. 't' appears 1 time? Put it on shelf 1.

Then walk from the top shelf (shelf n) down to shelf 1. Whatever characters you find on each shelf, write them out that many times. Characters on higher shelves come first in the result — exactly the descending-frequency order we need.

This is the Bucket Sort technique: instead of comparing elements, we distribute them into pre-arranged positions. It runs in O(n) time because both the counting and the bucket traversal are linear.

Step-by-Step Explanation

Let's trace through with s = "tree":

Step 1: Count frequencies in a single pass:

  • freq = {'t': 1, 'r': 1, 'e': 2}

Step 2: Create bucket array of size n+1 = 5 (indices 0..4):

  • bucket[0] = []
  • bucket[1] = []
  • bucket[2] = []
  • bucket[3] = []
  • bucket[4] = []

Step 3: Place characters into buckets by frequency:

  • 't' has frequency 1 → bucket[1] = ['t']
  • 'r' has frequency 1 → bucket[1] = ['t', 'r']
  • 'e' has frequency 2 → bucket[2] = ['e']

Buckets now: [0]=[], [1]=['t','r'], [2]=['e'], [3]=[], [4]=[]

Step 4: Iterate from highest bucket (4) down to 1:

  • bucket[4] = [] → skip
  • bucket[3] = [] → skip
  • bucket[2] = ['e'] → append 'e' × 2 = "ee"
  • bucket[1] = ['t', 'r'] → append 't' × 1 = "eet", then 'r' × 1 = "eetr"
  • bucket[0] always skipped (frequency 0 means the character doesn't exist)

Result: "eetr".

Bucket Sort — Distribute by Frequency, Collect Top-Down — Watch characters get placed into frequency buckets, then collected from highest to lowest bucket to produce the sorted result.

Algorithm

  1. Count frequency of each character using a hash map — O(n)
  2. Create a bucket array of size n+1 (index 0 to n)
  3. For each character in the frequency map, add it to the bucket at index = its frequency
  4. Iterate the bucket array from index n down to 1:
    • For each character in the current bucket, append it bucket_index times to the result
  5. Return the result

Code

#include <string>
#include <unordered_map>
#include <vector>
using namespace std;

class Solution {
public:
    string frequencySort(string s) {
        int n = s.size();
        
        // Step 1: Count frequencies
        unordered_map<char, int> freq;
        for (char c : s) {
            freq[c]++;
        }
        
        // Step 2: Create buckets — bucket[i] holds chars with frequency i
        vector<vector<char>> buckets(n + 1);
        for (auto& [ch, count] : freq) {
            buckets[count].push_back(ch);
        }
        
        // Step 3: Collect from highest bucket to lowest
        string result = "";
        for (int i = n; i >= 1; i--) {
            for (char ch : buckets[i]) {
                result += string(i, ch);
            }
        }
        
        return result;
    }
};
from collections import Counter

class Solution:
    def frequencySort(self, s: str) -> str:
        n = len(s)
        
        # Step 1: Count frequencies
        freq = Counter(s)
        
        # Step 2: Create buckets — bucket[i] holds chars with frequency i
        buckets = [[] for _ in range(n + 1)]
        for ch, count in freq.items():
            buckets[count].append(ch)
        
        # Step 3: Collect from highest bucket to lowest
        result = []
        for i in range(n, 0, -1):
            for ch in buckets[i]:
                result.append(ch * i)
        
        return ''.join(result)
import java.util.*;

class Solution {
    public String frequencySort(String s) {
        int n = s.length();
        
        // Step 1: Count frequencies
        Map<Character, Integer> freq = new HashMap<>();
        for (char c : s.toCharArray()) {
            freq.merge(c, 1, Integer::sum);
        }
        
        // Step 2: Create buckets — bucket[i] holds chars with frequency i
        List<List<Character>> buckets = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            buckets.add(new ArrayList<>());
        }
        for (Map.Entry<Character, Integer> entry : freq.entrySet()) {
            buckets.get(entry.getValue()).add(entry.getKey());
        }
        
        // Step 3: Collect from highest bucket to lowest
        StringBuilder result = new StringBuilder();
        for (int i = n; i >= 1; i--) {
            for (char ch : buckets.get(i)) {
                for (int j = 0; j < i; j++) {
                    result.append(ch);
                }
            }
        }
        
        return result.toString();
    }
}

Complexity Analysis

Time Complexity: O(n)

  • Counting frequencies: O(n) — one pass through the string
  • Distributing into buckets: O(k) — one pass through unique characters
  • Collecting from buckets: O(n) — we iterate through all n+1 buckets, but the total characters written is exactly n
  • Total: O(n + k + n) = O(n), since k ≤ n

No comparison-based sorting is used, so there is no O(k log k) term.

Space Complexity: O(n)

The bucket array has n+1 slots, each potentially holding characters. The frequency map uses O(k) space. The result string uses O(n). Total: O(n).

This is optimal: we must read all n characters (O(n) time) and produce an output of length n (O(n) space). No algorithm can do better.