Character Frequency Counting in DSA C

Mental Model

Count how many times each letter appears in a word or sentence by keeping track in a list.

Analogy: Imagine you have a box with many colored balls and you want to know how many balls of each color you have by putting them into separate jars labeled by color.

Input string: h e l l o \n
Frequency array: [a:0, b:0, c:0, ..., h:1, ..., l:2, ..., o:1, ..., z:0]

Dry Run Walkthrough

Input: string: "hello"

Goal: Count how many times each character appears in the string

Step 1: Read first character 'h', increase count for 'h'

[a:0, b:0, ..., h:1, ..., z:0]

Why: We start counting the first character to track its frequency

Step 2: Read second character 'e', increase count for 'e'

[a:0, b:0, ..., e:1, h:1, ..., z:0]

Why: Count the second character to update its frequency

Step 3: Read third character 'l', increase count for 'l'

[a:0, b:0, ..., e:1, h:1, l:1, ..., z:0]

Why: Count the third character to update its frequency

Step 4: Read fourth character 'l', increase count for 'l' again

[a:0, b:0, ..., e:1, h:1, l:2, ..., z:0]

Why: Second 'l' increases the count for 'l' to 2

Step 5: Read fifth character 'o', increase count for 'o'

[a:0, b:0, ..., e:1, h:1, l:2, o:1, ..., z:0]

Why: Count the last character to update its frequency

Result:

[a:0, b:0, c:0, d:0, e:1, f:0, g:0, h:1, i:0, j:0, k:0, l:2, m:0, n:0, o:1, p:0, q:0, r:0, s:0, t:0, u:0, v:0, w:0, x:0, y:0, z:0]

Annotated Code

DSA C

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

void countFrequency(const char *str, int freq[26]) {
    for (int i = 0; i < 26; i++) {
        freq[i] = 0; // initialize all counts to zero
    }
    for (int i = 0; str[i] != '\0'; i++) {
        char ch = str[i];
        if (ch >= 'a' && ch <= 'z') {
            freq[ch - 'a']++; // increase count for lowercase letters
        } else if (ch >= 'A' && ch <= 'Z') {
            freq[ch - 'A']++; // increase count for uppercase letters
        }
    }
}

void printFrequency(int freq[26]) {
    for (int i = 0; i < 26; i++) {
        if (freq[i] > 0) {
            printf("%c: %d\n", i + 'a', freq[i]);
        }
    }
}

int main() {
    const char *input = "hello";
    int freq[26];
    countFrequency(input, freq);
    printFrequency(freq);
    return 0;
}

freq[i] = 0; // initialize all counts to zero

reset frequency counts before starting

if (ch >= 'a' && ch <= 'z') { freq[ch - 'a']++; // increase count for lowercase letters }

increment count for lowercase characters

else if (ch >= 'A' && ch <= 'Z') { freq[ch - 'A']++; // increase count for uppercase letters }

increment count for uppercase characters

Output

e: 1

h: 1

l: 2

o: 1

Complexity Analysis

Time: O(n) because we scan each character in the string once

Space: O(1) because frequency array size is fixed at 26 letters

vs Alternative: Using a hash map would also be O(n) time but uses more space and is slower due to hashing overhead

Edge Cases

empty string

frequency array remains all zeros, no characters counted

DSA C

for (int i = 0; str[i] != '\0'; i++) {

string with uppercase letters

uppercase letters are counted correctly by converting to index

DSA C

else if (ch >= 'A' && ch <= 'Z') {

string with non-alphabet characters

non-alphabet characters are ignored and not counted

DSA C

if (ch >= 'a' && ch <= 'z') { ... } else if (ch >= 'A' && ch <= 'Z') { ... }

When to Use This Pattern

When you need to count how many times each letter appears in text, use character frequency counting to track counts efficiently.

Common Mistakes

Mistake: Not initializing the frequency array to zero before counting
Fix: Initialize all frequency counts to zero before starting the count loop

Mistake: Ignoring uppercase letters or treating them incorrectly
Fix: Add condition to handle uppercase letters by converting them to the same index range

Mistake: Counting non-alphabet characters which should be ignored
Fix: Add checks to count only alphabet characters and skip others

Summary

Counts how many times each letter appears in a string.

Use when you want to know the frequency of letters in words or sentences.

The key is to map each letter to an index in a fixed-size array and increment counts.