Character Frequency Counting in DSA C - Time & Space Complexity

Time Complexity: Character Frequency Counting

O(n)

Understanding Time Complexity

We want to understand how long it takes to count how often each character appears in a string.

The question is: how does the time needed grow as the string gets longer?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

void countFrequency(char *str) {
    int freq[256] = {0};
    int i;
    for(i = 0; str[i] != '\0'; i++) {
        freq[(unsigned char)str[i]]++;
    }
    for(i = 0; i < 256; i++) {
        if(freq[i] != 0) {
            printf("%c: %d\n", i, freq[i]);
        }
    }
}

int main() {
    char str[] = "hello world";
    countFrequency(str);
    return 0;
}
    

This code counts how many times each character appears in the input string and prints the counts.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The first loop goes through each character in the string once.
• How many times: It runs once for every character in the input string (n times).
• The second loop runs 256 times, which is a fixed number, not depending on input size.

How Execution Grows With Input

As the string gets longer, the first loop runs more times, directly matching the string length.

Input Size (n)	Approx. Operations
10	About 10 times for the first loop + 256 for the second
100	About 100 times for the first loop + 256 for the second
1000	About 1000 times for the first loop + 256 for the second

Pattern observation: The main work grows directly with the string length, while the second loop stays the same.

Final Time Complexity

Time Complexity: O(n)

This means the time to count characters grows in a straight line with the string length.

Common Mistake

[X] Wrong: "The second loop over 256 characters makes this O(n * 256) which is O(n²)."

[OK] Correct: The second loop runs a fixed 256 times, no matter how big the input is, so it does not multiply with n.

Interview Connect

Counting character frequency efficiently is a common task that shows you understand loops and arrays well.

Knowing how time grows helps you explain your code clearly in interviews.

Self-Check

"What if we used a linked list to store frequencies instead of an array? How would the time complexity change?"

Practice

1. What does character frequency counting help us find in a string?

easy

A. How many times each character appears

B. The length of the string

C. The first character in the string

D. The position of a character

Solution

1. Step 1: Understand character frequency counting

   It means counting how many times each character appears in a string.

2. Step 2: Compare with other options

   Length, first character, or position are different concepts, not frequency counting.

3. Final Answer:

   How many times each character appears -> Option A

4. Quick Check:

   Frequency counting = count of each character [OK]

Hint: Frequency means count of each character [OK]

Common Mistakes:

• Confusing frequency with string length
• Thinking frequency means position
• Mixing frequency with first character

2. Which of the following C code snippets correctly declares a frequency array for ASCII characters?

easy

A. int freq[256] = {0};

B. int freq = 256;

C. char freq[256];

D. int freq[] = {256};

Solution

1. Step 1: Understand frequency array declaration

   We need an integer array of size 256 initialized to zero to count ASCII characters.

2. Step 2: Check each option

   int freq[256] = {0}; declares int freq[256] = {0}; which is correct. Others either declare wrong types or wrong initialization.

3. Final Answer:

   int freq[256] = {0}; -> Option A

4. Quick Check:

   Array of 256 ints initialized to zero = int freq[256] = {0}; [OK]

Hint: Frequency array size 256 for ASCII, initialize with {0} [OK]

Common Mistakes:

• Using char array instead of int
• Not initializing array
• Wrong array size or syntax

3. What is the output frequency count for the string "aabbc" using a frequency array indexed by character ASCII values?

medium

A. {"a": 2, "b": 1, "c": 2}

B. {"a": 1, "b": 2, "c": 2}

C. {"a": 2, "b": 2, "c": 1}

D. {"a": 3, "b": 2, "c": 1}

Solution

1. Step 1: Count characters in the string "aabbc"

   Characters: 'a' appears 2 times, 'b' appears 2 times, 'c' appears 1 time.

2. Step 2: Match counts with options

   {"a": 2, "b": 2, "c": 1} matches the counts exactly. Others have incorrect counts.

3. Final Answer:

   {"a": 2, "b": 2, "c": 1} -> Option C

4. Quick Check:

   Count 'a'=2, 'b'=2, 'c'=1 [OK]

Hint: Count each character carefully, then match counts [OK]

Common Mistakes:

• Mixing counts of 'b' and 'c'
• Counting characters incorrectly
• Ignoring character case

4. Identify the error in this C code snippet for counting character frequency:

char str[] = "hello";
int freq[256];
for(int i = 0; i < 256; i++) freq[i] = 0;
for(int i = 0; i <= strlen(str); i++) freq[str[i]]++;

medium

A. Frequency array size should be 128, not 256

B. Loop should run till i < strlen(str), not <= strlen(str)

C. Frequency array should be of type char, not int

D. Initialization loop should start from i = 1

Solution

1. Step 1: Analyze loop condition for frequency counting

   The loop runs from i = 0 to i <= strlen(str), which includes the null character '\0' at the end.

2. Step 2: Understand why this causes error

   Accessing freq[str[i]] when str[i] is '\0' is valid but incrementing frequency for null char is usually unintended. Loop should run till i < strlen(str) to avoid counting null.

3. Final Answer:

   Loop should run till i < strlen(str), not <= strlen(str) -> Option B

4. Quick Check:

   Loop boundary off by one error [OK]

Hint: Use i < strlen(str) to avoid counting null char [OK]

Common Mistakes:

• Using <= instead of <
• Wrong array size assumption
• Wrong data type for freq array

5. Given a string with mixed uppercase and lowercase letters, how can you count character frequency ignoring case in C?

hard

A. Ignore characters that are uppercase

B. Count uppercase and lowercase separately

C. Use a frequency array of size 52 for letters

D. Convert each character to lowercase before counting frequency

Solution

1. Step 1: Understand ignoring case means treating 'A' and 'a' same

   To do this, convert each character to lowercase (or uppercase) before counting frequency.

2. Step 2: Check options for correct approach

   Convert each character to lowercase before counting frequency converts characters to lowercase before counting, which correctly ignores case. Others either separate counts or ignore characters incorrectly.

3. Final Answer:

   Convert each character to lowercase before counting frequency -> Option D

4. Quick Check:

   Case normalization before counting = Convert each character to lowercase before counting frequency [OK]

Hint: Normalize case before counting frequency [OK]

Common Mistakes:

• Counting uppercase and lowercase separately
• Ignoring uppercase letters
• Using wrong array size