Sort Characters by Frequency - Optimal HashMap and Heap Approach

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.

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.

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.

#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;
}

#include <iostream>
#include <unordered_map>
#include <queue>
#include <vector>
using namespace std;

string frequencySort(string s) {
  unordered_map<char, int> freqMap;
  for (char c : s) freqMap[c]++;

  priority_queue<pair<int, char>> maxHeap;
  for (auto &entry : freqMap) {
    maxHeap.push({entry.second, entry.first});
  }

  string result;
  while (!maxHeap.empty()) {
    auto [freq, ch] = maxHeap.top(); maxHeap.pop();
    result.append(freq, ch);
  }

  return result;
}

int main() {
  cout << "Sorted by frequency: " << frequencySort("tree") << endl;
  return 0;
}

from collections import Counter
import heapq

def frequency_sort(s):
    freq_map = Counter(s)
    max_heap = [(-freq, char) for char, freq in freq_map.items()]
    heapq.heapify(max_heap)

    result = []
    while max_heap:
        freq, char = heapq.heappop(max_heap)
        result.append(char * -freq)

    return ''.join(result)

print("Sorted by frequency:", frequency_sort("tree"))

import java.util.*;

public class SortCharactersByFrequency {
  public static String frequencySort(String s) {
    Map<Character, Integer> freqMap = new HashMap<>();
    for (char c : s.toCharArray()) {
      freqMap.put(c, freqMap.getOrDefault(c, 0) + 1);
    }

    PriorityQueue<Map.Entry<Character, Integer>> maxHeap =
      new PriorityQueue<>((a, b) -> b.getValue() - a.getValue());
    maxHeap.addAll(freqMap.entrySet());

    StringBuilder sb = new StringBuilder();
    while (!maxHeap.isEmpty()) {
      Map.Entry<Character, Integer> entry = maxHeap.poll();
      for (int i = 0; i < entry.getValue(); i++) {
        sb.append(entry.getKey());
      }
    }
    return sb.toString();
  }

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

function frequencySort(s) {
  const freqMap = {};
  for (let char of s) {
    freqMap[char] = (freqMap[char] || 0) + 1;
  }

  const sorted = Object.entries(freqMap).sort((a, b) => b[1] - a[1]);

  let result = '';
  for (let [char, freq] of sorted) {
    result += char.repeat(freq);
  }
  return result;
}

console.log("Sorted by frequency:", frequencySort("tree"));

package main

import (
  "fmt"
  "sort"
)

func frequencySort(s string) string {
  freq := make(map[rune]int)
  for _, ch := range s {
    freq[ch]++
  }

  type kv struct {
    Key   rune
    Value int
  }
  var sorted []kv
  for k, v := range freq {
    sorted = append(sorted, kv{k, v})
  }
  sort.Slice(sorted, func(i, j int) bool {
    return sorted[i].Value > sorted[j].Value
  })

  result := ""
  for _, kv := range sorted {
    for i := 0; i < kv.Value; i++ {
      result += string(kv.Key)
    }
  }
  return result
}

func main() {
  fmt.Println("Sorted by frequency:", frequencySort("tree"))
}

use std::collections::HashMap;

fn frequency_sort(s: &str) -> String {
  let mut freq = HashMap::new();
  for c in s.chars() {
    *freq.entry(c).or_insert(0) += 1;
  }

  let mut sorted: Vec<(char, i32)> = freq.into_iter().collect();
  sorted.sort_by(|a, b| b.1.cmp(&a.1));

  let mut result = String::new();
  for (ch, count) in sorted {
    result.push_str(&ch.to_string().repeat(count as usize));
  }
  result
}

fn main() {
  println!("Sorted by frequency: {}", frequency_sort("tree"));
}

fun frequencySort(s: String): String {
  val freqMap = mutableMapOf<Char, Int>()
  for (c in s) freqMap[c] = freqMap.getOrDefault(c, 0) + 1

  val sorted = freqMap.toList().sortedByDescending { it.second }
  val sb = StringBuilder()
  for ((ch, freq) in sorted) {
    repeat(freq) { sb.append(ch) }
  }
  return sb.toString()
}

fun main() {
  println("Sorted by frequency: ${frequencySort("tree")}")
}

func frequencySort(_ s: String) -> String {
  var freqMap: [Character: Int] = [:]
  for ch in s {
    freqMap[ch, default: 0] += 1
  }
  let sorted = freqMap.sorted { $0.value > $1.value }

  var result = ""
  for (ch, count) in sorted {
    result += String(repeating: ch, count: count)
  }
  return result
}

print("Sorted by frequency: \(frequencySort("tree"))")

function frequencySort(s: string): string {
  const freqMap: Record<string, number> = {};
  for (const char of s) {
    freqMap[char] = (freqMap[char] || 0) + 1;
  }
  const sorted = Object.entries(freqMap).sort((a, b) => b[1] - a[1]);
  let result = "";
  for (const [char, freq] of sorted) {
    result += char.repeat(freq);
  }
  return result;
}

console.log("Sorted by frequency:", frequencySort("tree"));

Time complexity

Space complexity

O(n + k)

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