Character Frequency Counting in DSA C++ - Time & Space Complexity

Time Complexity: Character Frequency Counting

O(n)

Understanding Time Complexity

Counting how often each character appears in a string is a common task. We want to know how the time needed grows as the string gets longer.

How does the work change when the input string size increases?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

void countFrequency(const std::string &s) {
    std::unordered_map<char, int> freq;
    for (char c : s) {
        freq[c]++;
    }
}
    

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

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Looping through each character in the string once.
• How many times: Exactly once for each character, so as many times as the string length.

How Execution Grows With Input

As the string gets longer, the number of steps grows directly with its length.

Input Size (n)	Approx. Operations
10	About 10 steps
100	About 100 steps
1000	About 1000 steps

Pattern observation: The work grows in a straight line with input size; doubling input doubles work.

Final Time Complexity

Time Complexity: O(n)

This means the time to count characters grows directly with the string length.

Common Mistake

[X] Wrong: "Since we use a map inside the loop, the time is more than linear, maybe quadratic."

[OK] Correct: Each map insertion or update is on average constant time, so it does not multiply the loop time.

Interview Connect

Understanding how simple loops and data structures affect time helps you explain your code clearly and choose the right approach in interviews.

Self-Check

"What if we used a sorted map instead of an unordered map? How would the time complexity change?"

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