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 or map.

Analogy: Imagine sorting colored beads into jars by color and counting how many beads go into each jar.

Input string: h e l l o
Frequency map:
{
  'h': 1,
  'e': 1,
  'l': 2,
  'o': 1
}

Dry Run Walkthrough

Input: string: "hello"

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

Step 1: Read first character 'h' and add it to frequency map with count 1

{'h': 1}

Why: We start counting characters as we see them

Step 2: Read second character 'e' and add it to frequency map with count 1

{'h': 1, 'e': 1}

Why: Add new character to map with count 1

Step 3: Read third character 'l' and add it to frequency map with count 1

{'h': 1, 'e': 1, 'l': 1}

Why: Add new character to map with count 1

Step 4: Read fourth character 'l' and increase count of 'l' to 2

{'h': 1, 'e': 1, 'l': 2}

Why: Character 'l' seen again, increase count

Step 5: Read fifth character 'o' and add it to frequency map with count 1

{'h': 1, 'e': 1, 'l': 2, 'o': 1}

Why: Add new character to map with count 1

Result:

Final frequency map: {'h': 1, 'e': 1, 'l': 2, 'o': 1}

Annotated Code

DSA C++

#include <iostream>
#include <unordered_map>
#include <string>

void countCharacterFrequency(const std::string& input) {
    std::unordered_map<char, int> freqMap;
    for (char ch : input) {
        freqMap[ch]++; // increase count for character
    }
    for (const auto& pair : freqMap) {
        std::cout << pair.first << ": " << pair.second << "\n";
    }
}

int main() {
    std::string input = "hello";
    countCharacterFrequency(input);
    return 0;
}

for (char ch : input) {

iterate over each character in the input string

freqMap[ch]++; // increase count for character

increment frequency count for current character

for (const auto& pair : freqMap) {

iterate over frequency map to print results

Output

h: 1

e: 1

l: 2

o: 1

Complexity Analysis

Time: O(n) because we scan each character once to count frequencies

Space: O(k) where k is number of unique characters, to store counts

vs Alternative: Using a map is faster than scanning the string multiple times for each character, which would be O(n*k)

Edge Cases

empty string

frequency map remains empty and nothing is printed

DSA C++

for (char ch : input) {

string with all same characters, e.g. "aaa"

frequency map has one entry with count equal to string length

DSA C++

freqMap[ch]++;

string with special characters or spaces

all characters including spaces and symbols are counted

DSA C++

freqMap[ch]++;

When to Use This Pattern

When you need to count how many times items appear in a collection, use frequency counting with a map to track counts efficiently.

Common Mistakes

Mistake: Not initializing count before incrementing, causing undefined behavior
Fix: Use map's default zero initialization by accessing freqMap[ch]++ which creates entry if missing

Mistake: Trying to count frequencies by nested loops scanning string repeatedly
Fix: Use a single pass with a map to count frequencies in O(n) time

Summary

Counts how many times each character appears in a string.

Use when you need to know the frequency of characters or items in a collection.

The key is to use a map to track counts as you scan the string once.

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