Character Frequency Counting in DSA C#

Mental Model

Count how many times each letter appears in a word or sentence by keeping track as you look at each letter once.

Analogy: Imagine sorting colored beads into jars by color, putting one bead in the jar each time you see that color.

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

Dry Run Walkthrough

Input: string: "hello"

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

Step 1: Look at first character 'h', add it to frequency map with count 1

{ 'h': 1 }

Why: We start counting characters from the beginning

Step 2: Look at second character 'e', add it to frequency map with count 1

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

Why: Add new character to map with count 1

Step 3: Look at third character 'l', 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: Look at fourth character 'l', increase count of 'l' by 1

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

Why: Character 'l' already counted, so increase count

Step 5: Look at fifth character 'o', 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:

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

Annotated Code

DSA C#

using System;
using System.Collections.Generic;

class CharacterFrequencyCounter
{
    public static Dictionary<char, int> CountFrequency(string input)
    {
        var frequencyMap = new Dictionary<char, int>();
        foreach (char c in input)
        {
            if (frequencyMap.ContainsKey(c))
            {
                frequencyMap[c] += 1; // increase count for existing character
            }
            else
            {
                frequencyMap[c] = 1; // add new character with count 1
            }
        }
        return frequencyMap;
    }

    static void Main()
    {
        string input = "hello";
        var result = CountFrequency(input);
        foreach (var pair in result)
        {
            Console.WriteLine($"'{pair.Key}': {pair.Value}");
        }
    }
}

foreach (char c in input)

iterate over each character in the input string

if (frequencyMap.ContainsKey(c))

check if character already counted

frequencyMap[c] += 1; // increase count for existing character

increment count for character already in map

frequencyMap[c] = 1; // add new character with count 1

add new character to map with initial count

Output

'h': 1

'e': 1

'l': 2

'o': 1

Complexity Analysis

Time: O(n) because we look at each character once in the input string of length n

Space: O(k) where k is the number of unique characters, because we store counts for each unique character

vs Alternative: Using a dictionary is faster than counting each character separately multiple times, which would be O(n*k)

Edge Cases

empty string

returns an empty frequency map with no characters

DSA C#

foreach (char c in input)

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

returns map with one character and count equal to string length

DSA C#

frequencyMap[c] += 1;

string with special characters and spaces, e.g. "a a!"

counts spaces and special characters as normal characters

DSA C#

if (frequencyMap.ContainsKey(c))

When to Use This Pattern

When you need to count how many times each item appears in a collection, use a frequency map (dictionary) to track counts efficiently.

Common Mistakes

Mistake: Forgetting to check if the character is already in the map before incrementing count
Fix: Always check with ContainsKey before incrementing, else add with count 1

Mistake: Using nested loops to count each character separately, causing slow performance
Fix: Use a single pass with a dictionary to count frequencies in one loop

Summary

Counts how many times each character appears in a string.

Use when you need to know the frequency of characters in text or data.

The key is to track counts as you see each character once using a dictionary.

Practice

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

easy

A. The length of the string

B. The first character of the string

C. How many times each character appears in the string

D. The position of a character in the string

Solution

1. Step 1: Understand character frequency counting

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

2. Step 2: Identify what is counted

   We count the occurrences of each character, not length or position.

3. Final Answer:

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

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 character position
• Mixing frequency with first character only

2. Which C# data structure is best to store character frequencies for a string?

easy

A. List<char>

B. Stack<char>

C. Queue<char>

D. Dictionary

Solution

1. Step 1: Identify data structure needs

   We need to map each character to its count, so key-value pairs are needed.

2. Step 2: Choose correct C# structure

   Dictionary stores characters as keys and counts as values.

3. Final Answer:

   Dictionary -> Option D

4. Quick Check:

   Use Dictionary for key-value pairs [OK]

Hint: Use Dictionary for char counts [OK]

Common Mistakes:

• Using List which stores only values, no keys
• Choosing Queue or Stack which are for order, not mapping
• Trying to use arrays without mapping keys

3. What is the output of this C# code?

string s = "hello";
var freq = new Dictionary();
foreach (char c in s) {
  if (freq.ContainsKey(c)) freq[c]++;
  else freq[c] = 1;
}
foreach (var pair in freq) {
  Console.Write(pair.Key + ":" + pair.Value + " ");
}

medium

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

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

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

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

Solution

1. Step 1: Count characters in "hello"

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

2. Step 2: Check code logic

   Code counts each character correctly and prints key:value pairs with spaces.

3. Final Answer:

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

4. Quick Check:

   Count 'l' twice, others once [OK]

Hint: Count each char carefully, 'l' appears twice [OK]

Common Mistakes:

• Counting 'l' only once
• Adding extra counts for characters
• Misreading output format

4. Find the error in this code that counts character frequency:

string s = "test";
var freq = new Dictionary();
foreach (char c in s) {
  freq[c]++;
}

medium

A. Dictionary not initialized

B. Incrementing freq[c] without checking if key exists

C. Using wrong loop variable

D. String s is empty

Solution

1. Step 1: Analyze dictionary usage

   freq[c]++ tries to increment value without checking if key exists first.

2. Step 2: Identify runtime error

   This causes a KeyNotFoundException because key may not exist initially.

3. Final Answer:

   Incrementing freq[c] without checking if key exists -> Option B

4. Quick Check:

   Check key before incrementing [OK]

Hint: Always check key before incrementing dictionary value [OK]

Common Mistakes:

• Assuming dictionary keys exist by default
• Ignoring KeyNotFoundException
• Not initializing dictionary

5. Given a string, how can you find the character with the highest frequency using C#?
Choose the best approach.

hard

A. Use a Dictionary to count frequencies, then find max value key

B. Sort the string and pick the first character

C. Use a List<char> to store characters and count manually

D. Use a Stack<char> to push characters and pop the most frequent

Solution

1. Step 1: Count frequencies with Dictionary

   Use Dictionary to store counts of each character.

2. Step 2: Find character with max frequency

   Iterate dictionary to find key with highest value.

3. Final Answer:

   Use a Dictionary to count frequencies, then find max value key -> Option A

4. Quick Check:

   Dictionary + max search = highest frequency [OK]

Hint: Count with Dictionary, then find max count key [OK]

Common Mistakes:

• Sorting string does not give frequency info
• Using List without mapping counts
• Stack is not suitable for frequency counting