Character Frequency Counting in DSA C - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of character frequency count in a string

What is the output of the following C code that counts character frequencies in a string?

DSA C

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

int main() {
    char str[] = "hello world";
    int freq[256] = {0};
    for (int i = 0; i < strlen(str); i++) {
        freq[(unsigned char)str[i]]++;
    }
    for (int i = 0; i < 256; i++) {
        if (freq[i] > 0) {
            printf("%c:%d ", i, freq[i]);
        }
    }
    return 0;
}

A h:1 e:1 l:3 o:1 :1 w:1 r:1 d:1

B h:1 e:1 l:2 o:2 :1 w:1 r:1 d:1

C h:1 e:1 l:3 o:2 :1 w:1 r:1 d:1

D h:1 e:1 l:3 o:2 :2 w:1 r:1 d:1

💡 Hint

Count each character's occurrences carefully, including spaces.

The string "hello world" has 1 'h', 1 'e', 3 'l's, 2 'o's, 2 spaces, 1 'w', 1 'r', and 1 'd'.

🧠 Conceptual

intermediate

Understanding character frequency array size

Why is the frequency array usually declared with size 256 when counting characters in C?

A Because it is the size of the string being processed.

B Because 256 is the maximum number of characters in any string.

C Because ASCII characters fit in 256 values, covering all possible characters in extended ASCII.

D Because 256 is the number of letters in the English alphabet.

💡 Hint

Think about the range of unsigned char values.

The array size 256 covers all possible values of an unsigned char (0 to 255), which includes all ASCII and extended ASCII characters.

🔧 Debug

advanced

Identify the error in character frequency counting code

What error will the following code produce when counting character frequencies?

DSA C

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

int main() {
    char str[] = "abcabc";
    int freq[128];
    for (int i = 0; i < strlen(str); i++) {
        freq[(int)str[i]]++;
    }
    for (int i = 0; i < 128; i++) {
        if (freq[i] > 0) {
            printf("%c:%d ", i, freq[i]);
        }
    }
    return 0;
}

A The code will print frequencies but with wrong characters due to casting.

B The code will cause a runtime error due to uninitialized freq array values.

C The code will cause a compilation error because freq array size is too small.

D The code will print correct frequencies without error.

💡 Hint

Check if freq array elements are initialized before incrementing.

The freq array is not initialized, so it contains garbage values. Incrementing them causes undefined behavior and likely wrong output or runtime errors.

❓ Predict Output

advanced

Output of frequency count with non-alphabet characters

What is the output of this C code counting frequencies including digits and punctuation?

DSA C

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

int main() {
    char str[] = "a1!a2!";
    int freq[256] = {0};
    for (int i = 0; i < strlen(str); i++) {
        freq[(unsigned char)str[i]]++;
    }
    for (int i = 0; i < 256; i++) {
        if (freq[i] > 0) {
            printf("%c:%d ", i, freq[i]);
        }
    }
    return 0;
}

A !:2 1:1 2:1 a:2

B a:2 !:2 1:1 2:1

C a:2 1:1 2:1 !:1

D 1:1 2:1 a:2 !:2

💡 Hint

Check the order of characters printed by increasing ASCII code.

Characters are printed in ASCII order: '!' (33), '1' (49), '2' (50), 'a' (97). Frequencies: '!'=2, '1'=1, '2'=1, 'a'=2.

🧠 Conceptual

expert

Memory optimization for character frequency counting

Which approach best reduces memory usage when counting frequencies of only lowercase English letters in a large text?

A Use an int array of size 26, indexing by (character - 'a').

B Use an int array of size 256 to cover all ASCII characters.

C Use a hash map with characters as keys and counts as values.

D Use a linked list to store characters and their counts dynamically.

💡 Hint

Focus on the smallest fixed-size array that covers only needed characters.

Using an int array of size 26 indexed by (character - 'a') uses minimal memory and is efficient for lowercase letters only.

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