Character Frequency Counting in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of character frequency count using map

What is the output of this C++ code that counts character frequency in a string?

DSA C++

std::string s = "hello";
std::map<char, int> freq;
for (char c : s) {
    freq[c]++;
}
for (auto &p : freq) {
    std::cout << p.first << ":" << p.second << " ";
}

A h:1 e:1 l:2 o:1

B o:1 l:2 e:1 h:1

C h:1 l:2 e:1 o:1

D e:1 h:1 l:2 o:1

💡 Hint

Remember std::map sorts keys in ascending order.

std::map stores keys sorted by default. Characters are sorted by ASCII codes: 'e'(101), 'h'(104), 'l'(108), 'o'(111). So output order is e, h, l, o.

❓ Predict Output

intermediate

Frequency count using unordered_map output order

What is the output of this C++ code counting character frequency using unordered_map?

DSA C++

std::string s = "abcabc";
std::unordered_map<char, int> freq;
for (char c : s) {
    freq[c]++;
}
for (auto &p : freq) {
    std::cout << p.first << ":" << p.second << " ";
}

A Output order is unspecified and may vary

B c:2 b:2 a:2

C b:2 a:2 c:2

D a:2 b:2 c:2

💡 Hint

unordered_map does not guarantee order of keys when iterating.

unordered_map stores keys in hash buckets, so iteration order is not guaranteed and may differ between runs or platforms.

🔧 Debug

advanced

Identify error in character frequency counting code

What error does this C++ code produce when counting character frequency?

DSA C++

std::string s = "test";
std::map<char, int> freq;
for (int i = 0; i < s.size(); i++) {
    freq[s[i]]++;
}

A Accesses out-of-bounds index causing undefined behavior

B Throws std::out_of_range exception

C Compilation error due to invalid map usage

D Runs correctly and counts frequencies

💡 Hint

Check loop boundary conditions carefully.

Loop uses i <= s.size(), so last iteration accesses s[s.size()] which is out-of-bounds causing undefined behavior.

🚀 Application

advanced

Find character with highest frequency

Given a string, which code snippet correctly finds the character with the highest frequency?

A

char maxChar = 0; int maxFreq = 0;
for (auto &p : freq) {
  if (p.first > maxFreq) {
    maxFreq = p.first;
    maxChar = p.second;
  }
}

B

char maxChar = 0; int maxFreq = INT_MAX;
for (auto &p : freq) {
  if (p.second < maxFreq) {
    maxFreq = p.second;
    maxChar = p.first;
  }
}

C

char maxChar = 0; int maxFreq = 0;
for (auto &p : freq) {
  if (p.second > maxFreq) {
    maxFreq = p.second;
    maxChar = p.first;
  }
}

D

char maxChar = 0; int maxFreq = 0;
for (auto &p : freq) {
  maxFreq = p.second;
  maxChar = p.first;
}

💡 Hint

Track the maximum frequency and update character accordingly.

Option C correctly updates maxFreq and maxChar when a higher frequency is found. Others either use wrong comparisons or overwrite without condition.

🧠 Conceptual

expert

Time complexity of character frequency counting

What is the time complexity of counting character frequency in a string of length n using std::unordered_map in C++?

A O(n^2) average case

B O(n) average case, O(n^2) worst case

C O(n log n) always

D O(log n) average case

💡 Hint

Consider average and worst case behavior of hash tables.

unordered_map provides average O(1) insert and access, so counting n characters is O(n) average. Worst case with many collisions can degrade to O(n^2).

Practice

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

easy

A. The length of the string

B. The position of a character in the string

C. The first character of the string

D. How many times each character appears in the string

Solution

1. Step 1: Understand character frequency counting

   It means counting how many times each character shows up in the string.

2. Step 2: Compare with options

   Only How many times each character appears in the string matches this meaning exactly.

3. Final Answer:

   How many times each character appears in the string -> Option D

4. Quick Check:

   Frequency counting = count characters [OK]

Hint: Frequency means count of each character [OK]

Common Mistakes:

• Confusing frequency with string length
• Thinking frequency means position
• Mixing frequency with substring extraction

2. Which of the following C++ code snippets correctly declares a map to count character frequencies?

easy

A. std::map freq;

B. std::vector freq;

C. std::map freq;

D. std::unordered_map<int> freq;

Solution

1. Step 1: Identify correct map declaration

   We need a map with key as char and value as int to count frequencies.

2. Step 2: Check each option

   std::map freq; uses std::map, which is correct. Others have wrong types or missing template parameters.

3. Final Answer:

   std::map freq; -> Option A

4. Quick Check:

   Map key=char, value=int for frequency [OK]

Hint: Map keys = characters, values = counts [OK]

Common Mistakes:

• Using vector instead of map
• Swapping key and value types
• Missing template parameters in map

3. What is the output of the following C++ code?

std::string s = "hello";
std::map freq;
for (char c : s) {
    freq[c]++;
}
for (auto &p : freq) {
    std::cout << p.first << ":" << p.second << " ";
}

medium

A. h:1 e:1 l:2 o:1

B. e:1 h:1 l:2 o:1

C. h:1 e:1 o:1 l:2

D. h:1 l:2 e:1 o:1

Solution

1. Step 1: Count characters in "hello"

   h=1, e=1, l=2, o=1

2. Step 2: Understand map iteration order

   std::map orders keys ascending by character: e, h, l, o

3. Final Answer:

   e:1 h:1 l:2 o:1 -> Option B

4. Quick Check:

   Map sorts keys alphabetically [OK]

Hint: Map prints keys sorted, not insertion order [OK]

Common Mistakes:

• Assuming insertion order output
• Mixing character counts
• Ignoring map key sorting

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

std::string s = "abcabc";
std::map freq;
for (int i = 0; i <= s.size(); i++) {
    freq[s[i]]++;
}

medium

A. freq[s[i]]++ should be freq[s[i]] = 1

B. Map should be unordered_map for frequency counting

C. Loop condition should be i < s.size(), not <= s.size()

D. String s should be a vector<char>

Solution

1. Step 1: Check loop boundary

   Loop runs from i=0 to i <= s.size(), which accesses s[s.size()] out of bounds.

2. Step 2: Correct loop condition

   It should be i < s.size() to avoid out-of-range access.

3. Final Answer:

   Loop condition should be i < s.size(), not <= s.size() -> Option C

4. Quick Check:

   Index must be less than string length [OK]

Hint: Use <, not <=, for string indexing loops [OK]

Common Mistakes:

• Off-by-one error in loop
• Wrong map type confusion
• Incorrect frequency increment logic

5. Given a string, how can you find the character with the highest frequency using C++ STL containers?

hard

A. Count frequencies in a map, then iterate to find max frequency character

B. Sort the string and pick the first character

C. Use a vector<char> to store characters and pick the last one

D. Use a queue to enqueue characters and dequeue the max frequency

Solution

1. Step 1: Count character frequencies using a map

   Use std::map to count how many times each character appears.

2. Step 2: Iterate map to find character with max frequency

   Loop through map entries to track character with highest count.

3. Final Answer:

   Count frequencies in a map, then iterate to find max frequency character -> Option A

4. Quick Check:

   Map + iteration finds max frequency char [OK]

Hint: Use map to count, then find max by scanning map [OK]

Common Mistakes:

• Sorting string doesn't give max frequency
• Using vector or queue wrongly
• Not iterating to find max frequency