Sort Characters by Frequency

Strings

Contents

VisualizationProblemExamplesSolutionAlgorithmCodeTimeSpace

Visualization Player

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

Solution❯

Understanding the Problem

We are given a string, and our task is to sort the characters in the string based on how frequently they appear. Characters that appear more often should come first in the result. If multiple characters have the same frequency, their relative order doesn't matter.

For example, if the input is "tree", the character 'e' appears twice, while 't' and 'r' appear once. A valid output would be "eetr" or "eert", as both start with the most frequent character.

Step-by-Step Solution with Example

Step 1: Count character frequencies

We first count how many times each character appears in the string. We can use a hash map (or dictionary) for this.

For the input "tree", we get: 


t → 1  
r → 1  
e → 2

Step 2: Organize characters by frequency

Now that we have the frequencies, we need a way to sort characters from highest to lowest frequency. A max heap (priority queue) is ideal for this because it allows us to always extract the character with the highest frequency.

Step 3: Build the output string

We extract characters from the max heap one by one. For each character, we repeat it as many times as its frequency and append it to the result string.

Continuing the example: 


Take 'e' → frequency 2 → append "ee"  
Then 't' or 'r' → frequency 1 → append "t" and "r"

Final output could be "eert" or "eetr".

Step 4: Return the final string

Once all characters are extracted and appended, return the final string as the answer.

Edge Cases

  • Empty string: If the input is "", the output should also be an empty string.
  • Single character: For input like "aaaa", the result is the same as input, "aaaa".
  • All characters same frequency: For input "abcde", any order is acceptable: "abcde", "edcba", etc.
  • Mixed characters: For input "a1a1b!", treat all characters equally. Count and sort based on frequency, not type.
  • Very large input: Ensure the solution handles large strings efficiently using heap or bucket sort.

Finally

This problem tests your understanding of frequency counting and using data structures like hash maps and heaps. The logic is straightforward: count → organize → build result. By carefully handling different input types and edge cases, we ensure the solution is both correct and robust.

Whether you’re a beginner or experienced coder, this step-by-step approach helps break the problem into manageable parts and makes the logic easy to follow.

Algorithm Steps❯

  1. Initialize a HashMap to store character frequencies.
  2. Traverse the input string and update character counts in the HashMap.
  3. Create a Max Heap (priority queue) where the comparison is based on frequency.
  4. Insert each character-frequency pair from the HashMap into the heap.
  5. 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).
  6. Return the final result string.

Code

C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
TS
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

struct CharFreq {
  char ch;
  int freq;
};

int compare(const void *a, const void *b) {
  return ((struct CharFreq *)b)->freq - ((struct CharFreq *)a)->freq;
}

void frequencySort(const char *s) {
  int count[256] = {0};
  for (int i = 0; s[i]; i++) {
    count[(unsigned char)s[i]]++;
  }
  
  struct CharFreq arr[256];
  int size = 0;
  for (int i = 0; i < 256; i++) {
    if (count[i] > 0) {
      arr[size].ch = i;
      arr[size].freq = count[i];
      size++;
    }
  }

  qsort(arr, size, sizeof(arr[0]), compare);
  for (int i = 0; i < size; i++) {
    for (int j = 0; j < arr[i].freq; j++) {
      printf("%c", arr[i].ch);
    }
  }
  printf("\n");
}

int main() {
  frequencySort("tree");
  return 0;
}

Time Complexity❯

CaseTime ComplexityExplanation
Best CaseO(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 CaseO(n log k)We count each character and sort based on frequency using a heap.
Worst CaseO(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)).


Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.

Loading comments...