Character Frequency Counting in DSA Javascript

Mental Model

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

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

word: h -> e -> l -> l -> o -> null
freq: {}

Dry Run Walkthrough

Input: word: 'hello'

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

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

freq: { h: 1 }

Why: We start counting letters from the beginning

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

freq: { h: 1, e: 1 }

Why: Add new letter to frequency count

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

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

Why: Add new letter to frequency count

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

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

Why: Letter 'l' seen again, increase count

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

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

Why: Add new letter to frequency count

Result:

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

Annotated Code

DSA Javascript

class CharFrequency {
  constructor() {
    this.freq = {};
  }

  countChars(word) {
    for (const char of word) {
      if (this.freq[char] !== undefined) {
        this.freq[char] += 1; // increase count if letter seen before
      } else {
        this.freq[char] = 1; // add new letter with count 1
      }
    }
    return this.freq;
  }
}

// Driver code
const word = 'hello';
const counter = new CharFrequency();
const result = counter.countChars(word);
console.log(result);

for (const char of word) {

iterate over each character in the word

if (this.freq[char] !== undefined) {

check if character already counted

this.freq[char] += 1; // increase count if letter seen before

increment count for repeated character

this.freq[char] = 1; // add new letter with count 1

initialize count for new character

Output

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

Complexity Analysis

Time: O(n) because we look at each letter once in the word of length n

Space: O(k) where k is number of unique letters, because we store counts for each unique letter

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

Edge Cases

empty string

returns empty frequency object {}

DSA Javascript

for (const char of word) {

string with all same letters like 'aaa'

returns frequency with one letter and count equal to string length

DSA Javascript

this.freq[char] += 1; // increase count if letter seen before

string with special characters or spaces

counts all characters including spaces and symbols

DSA Javascript

if (this.freq[char] !== undefined) {

When to Use This Pattern

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

Common Mistakes

Mistake: Forgetting to initialize count to 1 for new characters
Fix: Add else clause to set count to 1 when character is first seen

Mistake: Using nested loops to count each character separately
Fix: Use a single loop with a frequency map to count in one pass

Summary

Counts how many times each character appears in a string.

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

Keep a running count in a map as you look at each character once.

Practice

1. What does character frequency counting mean in simple terms?

easy

A. Sorting characters alphabetically

B. Counting how many times each character appears in a string

C. Replacing characters with numbers

D. Removing duplicate characters from a string

Solution

1. Step 1: Understand the meaning of frequency

   Frequency means how often something appears.

2. Step 2: Apply to characters in a string

   Counting frequency means counting how many times each character shows up in the string.

3. Final Answer:

   Counting how many times each character appears in a string -> Option B

4. Quick Check:

   Frequency counting = Counting characters [OK]

Hint: Frequency means count occurrences of each character [OK]

Common Mistakes:

• Confusing frequency with sorting
• Thinking frequency means removing duplicates
• Mixing frequency with character replacement

2. Which of the following JavaScript code snippets correctly initializes an empty object to store character frequencies?

easy

A. const freq = '';

B. const freq = [];

C. const freq = {};

D. const freq = null;

Solution

1. Step 1: Identify the data structure for frequency counting

   We use an object to store characters as keys and counts as values.

2. Step 2: Check correct syntax for empty object

   Empty object is created with curly braces {} in JavaScript.

3. Final Answer:

   const freq = {}; -> Option C

4. Quick Check:

   Empty object = {} [OK]

Hint: Use curly braces {} to create empty object [OK]

Common Mistakes:

• Using array [] instead of object {}
• Using empty string '' instead of object
• Assigning null which is not an object

3. What will be the output of the following code?

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

medium

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

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

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

D. SyntaxError

Solution

1. Step 1: Loop through each character in 'hello'

   Characters are 'h', 'e', 'l', 'l', 'o'.

2. Step 2: Count frequency using freq[ch] = (freq[ch] || 0) + 1

   For each character, add 1 to its count or start at 1 if not present.

3. Final Answer:

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

4. Quick Check:

   Count 'l' twice, others once [OK]

Hint: Use freq[ch] = (freq[ch] || 0) + 1 to count [OK]

Common Mistakes:

• Counting 'l' only once
• Getting syntax error from code
• Confusing keys and values in output

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

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

medium

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

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

C. Use let instead of const for freq

D. Missing semicolon after freq[ch] assignment

Solution

1. Step 1: Check loop range

   Loop runs from i = 0 to i <= str.length, which means i goes up to str.length (3 for 'abc').

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

   str[3] is undefined, so freq[undefined] is updated causing wrong key.

3. Final Answer:

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

4. Quick Check:

   Array index max is length - 1 [OK]

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

Common Mistakes:

• Using <= instead of < in loop
• Initializing freq as array instead of object
• Ignoring undefined character access

5. Given the string "aabbccddeeffgghhii", which code snippet correctly counts only characters that appear more than once and stores them in freq object?

hard

A. const freq = {};
for (const ch of str) {
freq[ch] = (freq[ch] || 0) + 1;
}
const filtered = {};
for (const ch in freq) {
if (freq[ch] > 1) filtered[ch] = freq[ch];
}

B. const freq = {};
for (const ch of str) {
if (freq[ch]) freq[ch]++;
else freq[ch] = 1;
}
for (const ch in freq) {
if (freq[ch] < 2) freq[ch] = 0;
}

C. const freq = {};
for (const ch of str) {
freq[ch] = 1;
}
for (const ch in freq) {
if (freq[ch] > 1) delete freq[ch];
}

D. const freq = {};
for (const ch of str) {
freq[ch] = (freq[ch] || 0) + 1;
}
for (const ch in freq) {
if (freq[ch] <= 1) delete freq[ch];
}

Solution

1. Step 1: Count all character frequencies

   Use freq[ch] = (freq[ch] || 0) + 1 to count all characters.

2. Step 2: Delete characters with frequency <= 1 from freq

   Iterate and delete keys where freq[ch] <= 1 to leave only duplicates in freq.

3. Final Answer:

   Code snippet that counts all then deletes singles from freq -> Option D

4. Quick Check:

   Delete freq <= 1 from freq [OK]

Hint: Count all, then delete characters with count <= 1 [OK]

Common Mistakes:

• Deleting keys while iterating freq object
• Setting frequency to 0 instead of removing
• Overwriting counts incorrectly