Sort Characters by Frequency

Problem Statement❯

Given a string s, your task is to sort the characters in the string based on how many times they appear, in descending order of frequency.

Characters that appear more frequently should come first in the result.
If multiple characters have the same frequency, their relative order can be arbitrary.

The result should be a new string where each character from the input is repeated as many times as it appeared originally, grouped together by frequency.

Examples❯

Input String	Possible Output(s)	Description
"tree"	"eert", "eetr"	'e' appears twice, 't' and 'r' once; 'e' comes first due to highest frequency
"cccaaa"	"cccaaa", "aaaccc"	'c' and 'a' both appear 3 times; characters with equal frequency can appear in any order
"Aabb"	"bbAa", "bbAa"	'b' appears twice; 'A' and 'a' once each—case is preserved, but frequency drives order
"abcde"	Any permutation like "abcde", "edcba"	All characters occur once; any order is valid since frequencies are equal
"aaaaaaa"	"aaaaaaa"	Only one character repeated; output remains the same
""	""	Empty input string; nothing to sort, so output is also empty
"112233!!@@"	"11@@!!2233", "223311!!@@"	Digits and symbols with equal frequencies; stable among same-frequency characters
"AaBbCc"	Any permutation	Each letter has the same frequency and case is preserved; order can vary

Visualization Player

Solution❯

To solve the problem of sorting characters by frequency, we need to count how often each character appears and then build a new string where the most frequent characters come first.

Understanding the Goal

Let’s say you are given a string like "tree". In this string, 'e' appears twice while 't' and 'r' appear once each. Since we want characters sorted by frequency, 'e' should come before the others. The output might look like "eetr" or "eert".

Handling Different Cases

Case 1: Characters with different frequencies
This is the most straightforward case. You count how many times each character occurs and then order them from highest to lowest. For example, in "cccaaa", both 'c' and 'a' appear three times, so the result could be "cccaaa" or "aaaccc".
Case 2: All characters have the same frequency
When every character appears once, like in "abcde", any order is acceptable. Since they all have the same frequency, there’s no preferred arrangement.
Case 3: Single repeating character
If the string has only one unique character repeated multiple times (like "aaaaaaa"), then the output will be the same as the input. There's nothing to reorder because all characters are identical.
Case 4: Mixed characters (letters, digits, symbols)
This includes strings like "112233!!@@". You count each character, regardless of whether it’s a letter, number, or symbol. As long as you correctly count and sort by frequency, the result will be valid.
Case 5: Empty string
If the input string is empty, then the output should also be an empty string. There are no characters to count or sort.

How We Approach the Problem

First, we count how many times each character appears. This can be done using a HashMap or dictionary. Then, we want to get the characters with the highest frequency first. To do this efficiently, we use a structure like a Max Heap (also called a priority queue), which always gives us the most frequent character available next.

Finally, we keep pulling characters from the heap, repeating each one based on how often it appeared, and building the result string step by step.

Why This Works

We are guaranteed to get the most frequent characters first because of how the heap is built. Even if characters have the same frequency, any valid order between them is accepted. This method ensures we don’t miss any character and that we arrange them efficiently.

Algorithm Steps❯

Initialize a HashMap to store character frequencies.
Traverse the input string and update character counts in the HashMap.
Create a Max Heap (priority queue) where the comparison is based on frequency.
Insert each character-frequency pair from the HashMap into the heap.
While the heap is not empty, remove the character with the highest frequency and append it to the result string multiple times (equal to its frequency).
Return the final result string.

Code

Java

Python

JavaScript

C++

Kotlin

Swift

Php

import java.util.*;

public class SortCharactersByFrequency {
  public static String frequencySort(String s) {
    Map<Character, Integer> freqMap = new HashMap<>();

    // Count frequency of each character
    for (char c : s.toCharArray()) {
      freqMap.put(c, freqMap.getOrDefault(c, 0) + 1);
    }

    // Max Heap based on character frequency
    PriorityQueue<Map.Entry<Character, Integer>> maxHeap =
      new PriorityQueue<>((a, b) -> b.getValue() - a.getValue());

    maxHeap.addAll(freqMap.entrySet());

    // Build result
    StringBuilder sb = new StringBuilder();
    while (!maxHeap.isEmpty()) {
      Map.Entry<Character, Integer> entry = maxHeap.poll();
      char ch = entry.getKey();
      int freq = entry.getValue();
      for (int i = 0; i < freq; i++) {
        sb.append(ch);
      }
    }

    return sb.toString();
  }

  public static void main(String[] args) {
    String input = "tree";
    System.out.println("Sorted by frequency: " + frequencySort(input));
  }
}

Time Complexity❯

Case	Time Complexity	Explanation
Best Case	O(n log k)	Where n is the length of the string and k is the number of unique characters. HashMap takes O(n), heap insertion takes O(log k).
Average Case	O(n log k)	We count each character and sort based on frequency using a heap.
Worst Case	O(n log k)	Even in the worst case, we do not exceed n log k because heap operations dominate after counting frequencies.

Space Complexity❯

O(n + k)

Explanation: We use space for the HashMap (O(k)), heap (O(k)), and the output string (O(n)).

⬅ Previous TopicCheck if Two Strings Are Anagrams - Optimal Approach

Next Topic ⮕Find Longest Palindromic Substring - Dynamic Programming Approach