Character Frequency Counting in DSA Typescript

Mental Model

Count how many times each letter appears in a word by remembering each letter and adding one every time it shows up.

Analogy: Imagine you have a basket and every time you see a fruit, you put a sticker on it. At the end, the stickers tell you how many of each fruit you have.

word: h e l l o
freq: {}

Dry Run Walkthrough

Input: word: hello

Goal: Find how many times each letter appears in 'hello'

Step 1: Look at 'h', add 'h' to frequency with count 1

freq: { h: 1 }

Why: First time seeing 'h', start counting it

Step 2: Look at 'e', add 'e' to frequency with count 1

freq: { h: 1, e: 1 }

Why: First time seeing 'e', start counting it

Step 3: Look at 'l', add 'l' to frequency with count 1

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

Why: First time seeing 'l', start counting it

Step 4: Look at next 'l', increase count of 'l' to 2

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

Why: Seen 'l' before, add one more

Step 5: Look at 'o', add 'o' to frequency with count 1

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

Why: First time seeing 'o', start counting it

Result:

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

Annotated Code

DSA Typescript

class CharFrequency {
  static countChars(word: string): Record<string, number> {
    const freq: Record<string, number> = {};
    for (const char of word) {
      if (freq[char] === undefined) {
        freq[char] = 1; // first time seeing char, start count
      } else {
        freq[char] += 1; // seen before, add one
      }
    }
    return freq;
  }
}

// Driver code
const word = "hello";
const result = CharFrequency.countChars(word);
for (const char in result) {
  console.log(`${char}: ${result[char]}`);
}

for (const char of word) {

iterate over each character in the word

if (freq[char] === undefined) {

check if character is new to frequency map

freq[char] = 1; // first time seeing char, start count

initialize count for new character

freq[char] += 1; // seen before, add one

increment count for existing character

Output

h: 1

e: 1

l: 2

o: 1

Complexity Analysis

Time: O(n) because we look at each character once

Space: O(k) where k is number of unique characters in the word

vs Alternative: Better than nested loops that count each character separately, which would be O(n^2)

Edge Cases

empty string

returns empty frequency map

DSA Typescript

for (const char of word) {

string with all same characters

frequency count shows one character with count equal to string length

DSA Typescript

freq[char] += 1; // seen before, add one

string with special characters or spaces

counts those characters as normal characters

DSA Typescript

if (freq[char] === undefined) {

When to Use This Pattern

When you need to count how many times each item appears in a list or string, use character frequency counting to track counts efficiently.

Common Mistakes

Mistake: Forgetting to initialize count for new characters before incrementing
Fix: Check if character is new and set count to 1 before adding

Mistake: Using nested loops to count frequencies causing slow performance
Fix: Use a single pass with a map/dictionary to count frequencies

Summary

Counts how many times each character appears in a string.

Use when you need to know frequency of letters or symbols in text.

The key is to remember counts as you see characters once, then add up.

Practice

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

easy

A. How many times each character appears in the string

B. The length of the string

C. The first character of the string

D. The position of a character in the string

Solution

1. Step 1: Understand character frequency counting

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

2. Step 2: Identify what it helps find

   This counting helps us know the number of occurrences of each character, not the length or position.

3. Final Answer:

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

4. Quick Check:

   Frequency counting = character counts [OK]

Hint: Frequency counting means counting each character's occurrences [OK]

Common Mistakes:

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

2. Which TypeScript code snippet correctly initializes an empty object to store character frequencies?

easy

A. const freq = new Map();

B. const freq = {};

C. const freq = [];

D. const freq = '';

Solution

1. Step 1: Identify data structure for frequency counting

   We need an object to store keys (characters) and values (counts). An empty object is initialized with {}.

2. Step 2: Check each option

   const freq = new Map(); uses Map which is valid but not the simplest empty object. const freq = {}; correctly uses {}. const freq = []; is an array, not suitable. const freq = ''; is a string, not suitable.

3. Final Answer:

   const freq = {}; -> Option B

4. Quick Check:

   Empty object = {} [OK]

Hint: Use {} to start an empty object for frequency counts [OK]

Common Mistakes:

• Using array [] instead of object {}
• Using empty string '' instead of object
• Confusing Map with plain object initialization

3. What is the output of this TypeScript code?

const str = 'hello';
const freq: {[key: string]: number} = {};
for (const ch of str) {
  freq[ch] = (freq[ch] || 0) + 1;
}
console.log(freq);

medium

A. {"h":1,"e":1,"l":3,"o":1}

B. {"h":1,"e":1,"l":1,"o":1}

C. {"h":1,"e":1,"l":2,"o":1}

D. {"h":0,"e":0,"l":0,"o":0}

Solution

1. Step 1: Loop through each character and count

   Characters: 'h', 'e', 'l', 'l', 'o'. For each, increase count in freq object.

2. Step 2: Calculate counts

   'h' = 1, 'e' = 1, 'l' = 2 (appears twice), 'o' = 1.

3. Final Answer:

   {"h":1,"e":1,"l":2,"o":1} -> Option C

4. Quick Check:

   Count 'l' twice = 2 [OK]

Hint: Add 1 or start at 0 for each char count [OK]

Common Mistakes:

• Counting 'l' only once
• Setting counts to zero
• Miswriting object output format

4. Find the error in this TypeScript code for counting character frequency:

const str = 'abc';
const freq: {[key: string]: number} = {};
for (let i = 0; i <= str.length; i++) {
  const ch = str[i];
  freq[ch] = (freq[ch] || 0) + 1;
}
console.log(freq);

medium

A. Use 'for...in' instead of 'for' loop

B. freq should be initialized as an array, not object

C. Missing declaration of variable ch

D. Loop condition should be i < str.length, not i <= str.length

Solution

1. Step 1: Check loop bounds

   Loop runs from i = 0 to i <= str.length, which means i goes up to str.length (3). But string indices go from 0 to length-1 (2).

2. Step 2: Identify out-of-bounds access

   At i = 3, str[3] is undefined, causing freq[undefined] to be updated, which is incorrect.

3. Final Answer:

   Loop condition should be i < str.length, not i <= str.length -> Option D

4. Quick Check:

   Loop index must be less than length [OK]

Hint: Use i < length to avoid out-of-bounds errors [OK]

Common Mistakes:

• Using <= instead of < in loop condition
• Initializing freq as array instead of object
• Confusing for...in with for...of loops

5. Given the string "aabbc", which TypeScript code snippet correctly returns an object with only characters that appear exactly twice?

hard

A. const freq: {[key: string]: number} = {};
for (const ch of str) {
freq[ch] = (freq[ch] || 0) + 1;
}
const result = Object.fromEntries(Object.entries(freq).filter(([k,v]) => v === 2));

B. const freq = new Map();
for (const ch of str) {
freq.set(ch, (freq.get(ch) || 0) + 1);
}
const result = Object.fromEntries([...freq].filter(([k,v]) => v === 1));

C. const freq = {};
for (const ch of str) {
freq[ch] = 2;
}
const result = freq;

D. const freq = {};
for (const ch of str) {
freq[ch] = (freq[ch] || 0) + 1;
}
const result = Object.keys(freq);

Solution

1. Step 1: Count frequencies correctly

   Loop through string, count each character's occurrences in freq object.

2. Step 2: Filter characters with count exactly 2

   Use Object.entries(freq) to get pairs, filter those with value 2, then convert back to object.

3. Final Answer:

   Code snippet that counts and filters for count === 2 -> Option A

4. Quick Check:

   Filter freq entries where value is 2 [OK]

Hint: Filter entries with value === 2 after counting [OK]

Common Mistakes:

• Filtering for count === 1 instead of 2
• Assigning fixed count 2 inside loop
• Returning keys instead of filtered object