Character Frequency Counting in DSA Python - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is character frequency counting?

It is the process of counting how many times each character appears in a given string.

beginner

Which data structure is commonly used to store character frequencies?

A dictionary (or map) is commonly used, where keys are characters and values are their counts.

beginner

How do you update the count of a character in a dictionary during frequency counting?

Check if the character is already a key; if yes, increase its value by 1; if not, add it with value 1.

intermediate

Why is character frequency counting useful?

It helps in tasks like text analysis, compression, and detecting duplicates or patterns in data.

intermediate

What is the time complexity of counting character frequencies in a string of length n?

The time complexity is O(n) because each character is processed once.

What data structure is best for counting character frequencies in Python?

A Set

B List

C Tuple

D Dictionary

A dictionary stores characters as keys and counts as values, making it ideal for frequency counting.

If the input string is 'hello', what is the frequency of 'l'?

A 2

B 0

C 3

D 1

The character 'l' appears twice in 'hello'.

What is the first step in counting character frequencies?

A Sort the string

B Remove spaces

C Initialize an empty dictionary

D Convert string to uppercase

You start by creating an empty dictionary to store counts.

What happens if a character is not yet in the frequency dictionary?

A Ignore it

B Add it with count 1

C Add it with count 0

D Remove it from string

New characters are added with a count of 1 when first encountered.

What is the time complexity of counting frequencies in a string of length n?

A O(n)

B O(n^2)

C O(n log n)

D O(1)

Each character is processed once, so the complexity is linear, O(n).

Explain how to count character frequencies in a string step-by-step.

Think about how you would tally votes for each character.

Why is using a dictionary efficient for character frequency counting?

Consider how quickly you can find and update counts.

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 the last character

Solution

1. Step 1: Understand the purpose of frequency counting

   Frequency counting means counting how many times each character appears in a string.

2. Step 2: Compare options with the definition

   Only How many times each character appears matches the purpose of character frequency counting.

3. Final Answer:

   How many times each character appears -> Option A

4. Quick Check:

   Frequency counting = count characters [OK]

Hint: Frequency counting means counting characters [OK]

Common Mistakes:

• Confusing frequency with string length
• Thinking it finds character positions
• Mixing frequency with sorting

2. Which of the following Python code snippets correctly counts character frequency in string s?

easy

A. freq = 0; for ch in s: freq += 1

B. freq = []; for ch in s: freq.append(ch)

C. freq = {}; for ch in s: freq[ch] = freq.get(ch, 0) + 1

D. freq = {}; for ch in s: freq[ch] = 1

Solution

1. Step 1: Analyze each code snippet

   freq = {}; for ch in s: freq[ch] = freq.get(ch, 0) + 1 uses a dictionary and increments count for each character correctly. freq = []; for ch in s: freq.append(ch) just collects characters in a list. freq = 0; for ch in s: freq += 1 counts total characters, not frequency per character. freq = {}; for ch in s: freq[ch] = 1 sets frequency to 1 always, ignoring repeats.

2. Step 2: Confirm correct frequency counting logic

   Only freq = {}; for ch in s: freq[ch] = freq.get(ch, 0) + 1 correctly counts how many times each character appears.

3. Final Answer:

   freq = {}; for ch in s: freq[ch] = freq.get(ch, 0) + 1 -> Option C

4. Quick Check:

   Use dict with get() to count [OK]

Hint: Use dict with get() to count frequencies [OK]

Common Mistakes:

• Using list instead of dict for counting
• Overwriting counts instead of incrementing
• Counting total length instead of per character

3. What is the output of this code?

text = 'hello'
freq = {}
for ch in text:
    freq[ch] = freq.get(ch, 0) + 1
print(freq)

medium

A. {'h': 1, 'e': 1, 'l': 1, 'o': 1}

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

C. {'h': 1, 'e': 1, 'l': 3, 'o': 1}

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

Solution

1. Step 1: Count characters in 'hello'

   Characters: h(1), e(1), l(2), o(1)

2. Step 2: Check code logic

   Code correctly counts each character's frequency using dict and get().

3. Final Answer:

   {'h': 1, 'e': 1, 'l': 2, 'o': 1} -> Option B

4. Quick Check:

   Count 'l' twice, others once [OK]

Hint: Count repeated letters carefully [OK]

Common Mistakes:

• Counting 'l' only once
• Missing last character
• Incorrect dictionary format

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

text = 'apple'
freq = {}
for ch in text:
    freq[ch] += 1
print(freq)

medium

A. freq[ch] is used before initialization

B. Loop variable name is wrong

C. print statement syntax error

D. String 'apple' is invalid

Solution

1. Step 1: Identify how freq[ch] is updated

   freq[ch] += 1 tries to add 1 to freq[ch] without initializing freq[ch] first.

2. Step 2: Understand dictionary key initialization

   Since freq is empty initially, freq[ch] does not exist and causes an error.

3. Final Answer:

   freq[ch] is used before initialization -> Option A

4. Quick Check:

   Initialize dict keys before incrementing [OK]

Hint: Initialize dict keys before incrementing [OK]

Common Mistakes:

• Assuming dict keys auto-initialize
• Ignoring error messages
• Changing loop variable unnecessarily

5. Given a string s = 'banana', which code snippet correctly returns a dictionary with only characters that appear more than once?

hard

A. freq = {ch: 1 for ch in s if s.count(ch) > 1}

B. freq = {ch: s.count(ch) for ch in s}

C. freq = {ch for ch in s if s.count(ch) > 1}

D. freq = {ch: s.count(ch) for ch in set(s) if s.count(ch) > 1}

Solution

1. Step 1: Understand the goal

   We want a dictionary with characters appearing more than once and their counts.

2. Step 2: Analyze each option

   freq = {ch: 1 for ch in s if s.count(ch) > 1} sets count to 1 always, ignoring actual counts. freq = {ch: s.count(ch) for ch in set(s) if s.count(ch) > 1} uses set(s) to avoid duplicates and filters counts > 1 correctly. freq = {ch for ch in s if s.count(ch) > 1} creates a set instead of dictionary with counts. freq = {ch: s.count(ch) for ch in s} includes all characters regardless of count.

3. Final Answer:

   freq = {ch: s.count(ch) for ch in set(s) if s.count(ch) > 1} -> Option D

4. Quick Check:

   Use set to avoid duplicates and filter counts [OK]

Hint: Use set(s) and filter counts > 1 [OK]

Common Mistakes:

• Not using set to avoid duplicate keys
• Assigning wrong counts
• Including characters with single occurrence