#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>
/* Pair structure: (letter, frequency) */
typedef struct {
char letter;
int freq;
} Pair;
/* Comparator for qsort — sort by frequency descending */
int comparePairs(const void *a, const void *b) {
const Pair *pa = (const Pair *)a;
const Pair *pb = (const Pair *)b;
return pb->freq - pa->freq; /* descending */
}
/* sortByFrequency — counts how often each letter appears and returns a sorted list */
void sortByFrequency(const char *s, Pair result[26]) {
int freq[26] = {0}; /* frequency array for 26 lowercase letters */
/* Iterate through the string and count only alphabetic characters */
for (const char *p = s; *p; p++) {
if (isalpha((unsigned char)*p)) {
freq[tolower((unsigned char)*p) - 'a']++;
}
}
/* Build array of (letter, frequency) pairs */
for (int i = 0; i < 26; i++) {
result[i].letter = 'a' + i;
result[i].freq = freq[i];
}
/* Sort pairs by frequency in descending order */
qsort(result, 26, sizeof(Pair), comparePairs);
}
/* Build a string sorted by frequency: ddddddddddddccccccbbbbbaaaafffeehhgs */
char *buildSortedString(const Pair sorted[26]) {
int total = 0;
/* Count total characters needed */
for (int i = 0; i < 26; i++)
total += sorted[i].freq;
/* Allocate output string (+1 for null terminator) */
char *out = malloc(total + 1);
if (!out) return NULL;
char *p = out;
/* Append each letter repeated freq times */
for (int i = 0; i < 26; i++) {
if (sorted[i].freq > 0) {
memset(p, sorted[i].letter, sorted[i].freq);
p += sorted[i].freq;
}
}
*p = '\0';
return out;
}
int main(void) {
const char *text = "bbcabddddccafffadbbcdccsedddddhhgade";
Pair sorted[26];
sortByFrequency(text, sorted);
/* Print each letter and its frequency */
for (int i = 0; i < 26; i++) {
if (sorted[i].freq != 0)
printf("%c: %d\n", sorted[i].letter, sorted[i].freq);
}
/* Print the reconstructed sorted string */
char *letters_sorted_by_frequency = buildSortedString(sorted);
printf("\nSorted string: %s\n", letters_sorted_by_frequency);
free(letters_sorted_by_frequency);
return 0;
}
/*
run:
d: 12
c: 6
b: 5
a: 4
f: 3
e: 2
h: 2
g: 1
s: 1
Sorted string: ddddddddddddccccccbbbbbaaaafffeehhgs
*/
