Sort Characters By Frequency - Practice Coding Problems

Sort Characters By Frequency - Problem

Hash Table String Sorting Heap (Priority Queue) Bucket Sort Counting Medium

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.

Input & Output

Example 1 — Basic Case

$ Input: s = "tree"

› Output: "eetr" or "eert"

💡 Note: Character frequencies: e→2, t→1, r→1. Sort by frequency: e(2) comes first, then t(1) and r(1) in any order.

Example 2 — All Different Frequencies

$ Input: s = "cccaaa"

› Output: "aaaccc" or "cccaaa"

💡 Note: Both 'c' and 'a' appear 3 times, so they can be in any order, resulting in "aaaccc" or "cccaaa".

Example 3 — Single Character

$ Input: s = "Aabb"

› Output: "bbAa" or "bbaA"

💡 Note: Frequencies: b→2, A→1, a→1. Character 'b' appears most frequently, then 'A' and 'a' in any order.

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input Analysis

Parse input string and identify character frequencies

Frequency Sorting

Sort characters by their occurrence frequency

String Reconstruction

Build output with most frequent characters first

Key Takeaway

🎯 Key Insight: Count frequencies first, then sort by count to prioritize most frequent characters

Asked in

a Amazon 45 G Google 38 f Facebook 32 M Microsoft 28

The key insight is to count character frequencies first, then sort by frequency. The hash map approach is most practical with O(n + k log k) time complexity. For bounded frequency ranges, bucket sort achieves O(n) time.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Count Each Character Repeatedly	O(n²)	O(k)	For each unique character, count its frequency by scanning the entire string
Bucket Sort by Frequency	O(n)	O(n)	Use bucket sort to achieve linear time sorting when frequency range is limited
Hash Map Frequency Count	O(n + k log k)	O(k)	Count character frequencies using a hash map, then sort by frequency
Priority Queue (Max Heap)	O(n + k log k)	O(k)	Use a max heap to automatically sort characters by frequency

Brute Force - Count Each Character Repeatedly — Algorithm Steps

Find all unique characters in the string
For each character, count its frequency by scanning the entire string
Sort characters by frequency in descending order
Build result string by repeating each character according to its frequency

Visualization

Tap to expand

Step-by-Step Walkthrough

Find Unique

Extract all unique characters from string

Count Each

For each unique char, scan entire string to count

Sort & Build

Sort by frequency and construct result

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    char ch;
    int freq;
} CharFreq;

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

char* solution(char* s) {
    int len = strlen(s);
    if (len == 0) return s;
    
    // Find unique characters
    int visited[256] = {0};
    char unique[256];
    int uniqueCount = 0;
    
    for (int i = 0; i < len; i++) {
        if (!visited[(unsigned char)s[i]]) {
            visited[(unsigned char)s[i]] = 1;
            unique[uniqueCount++] = s[i];
        }
    }
    
    // Count frequency of each character
    CharFreq charFreq[256];
    for (int i = 0; i < uniqueCount; i++) {
        charFreq[i].ch = unique[i];
        charFreq[i].freq = 0;
        for (int j = 0; j < len; j++) {
            if (s[j] == unique[i]) {
                charFreq[i].freq++;
            }
        }
    }
    
    // Sort by frequency
    qsort(charFreq, uniqueCount, sizeof(CharFreq), compare);
    
    // Build result
    char* result = (char*)malloc((len + 1) * sizeof(char));
    int pos = 0;
    for (int i = 0; i < uniqueCount; i++) {
        for (int j = 0; j < charFreq[i].freq; j++) {
            result[pos++] = charFreq[i].ch;
        }
    }
    result[pos] = '\0';
    
    return result;
}

int main() {
    char s[100001];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    
    char* result = solution(s);
    printf("%s\n", result);
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

For each of k unique characters, scan n characters to count frequency

⚠ Quadratic Growth

Space Complexity

O(k)

Store k unique characters and their counts

✓ Linear Space

89.0K Views

High Frequency

~15 min Avg. Time

3.4K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Count Each Character Repeatedly — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler