Character Frequency Counting in DSA Go - Execution Trace

Concept Flow - Character Frequency Counting

Start with empty frequency map

↓

Read next character from string

↓

Is character in map?

No→Add character with count 1

|Yes↓

Increment character count by 1

↓

More characters?

Yes→Read next character

No↓

Done: frequency map ready

We read each character one by one, update its count in a map, and repeat until all characters are processed.

Execution Sample

DSA Go

input := "hello"
freq := map[rune]int{}
for _, ch := range input {
    freq[ch]++
}
fmt.Println(freq)

Counts how many times each character appears in the string "hello".

Execution Table

Step	Operation	Character	Frequency Map State	Visual State
1	Start	-	{}	{}
2	Read character	'h'	{}	{}
3	Add 'h' with count 1	'h'	{'h':1}	{'h':1}
4	Read character	'e'	{'h':1}	{'h':1}
5	Add 'e' with count 1	'e'	{'h':1, 'e':1}	{'h':1, 'e':1}
6	Read character	'l'	{'h':1, 'e':1}	{'h':1, 'e':1}
7	Add 'l' with count 1	'l'	{'h':1, 'e':1, 'l':1}	{'h':1, 'e':1, 'l':1}
8	Read character	'l'	{'h':1, 'e':1, 'l':1}	{'h':1, 'e':1, 'l':1}
9	Increment 'l' count	'l'	{'h':1, 'e':1, 'l':2}	{'h':1, 'e':1, 'l':2}
10	Read character	'o'	{'h':1, 'e':1, 'l':2}	{'h':1, 'e':1, 'l':2}
11	Add 'o' with count 1	'o'	{'h':1, 'e':1, 'l':2, 'o':1}	{'h':1, 'e':1, 'l':2, 'o':1}
12	No more characters	-	{'h':1, 'e':1, 'l':2, 'o':1}	{'h':1, 'e':1, 'l':2, 'o':1}

💡 All characters processed, frequency map complete.

Variable Tracker

Variable	Start	After Step 3	After Step 5	After Step 7	After Step 9	After Step 11	Final
freq	{}	{'h':1}	{'h':1, 'e':1}	{'h':1, 'e':1, 'l':1}	{'h':1, 'e':1, 'l':2}	{'h':1, 'e':1, 'l':2, 'o':1}	{'h':1, 'e':1, 'l':2, 'o':1}
ch	-	'h'	'e'	'l'	'l'	'o'	-

Key Moments - 3 Insights

Why do we add a character with count 1 instead of incrementing directly?

Because the character is not yet in the map, so incrementing would fail. We first add it with count 1 as shown in steps 3, 5, 7, and 11.

Why do we increment the count for 'l' at step 9 instead of adding it again?

Because 'l' is already in the map from step 7, so we increase its count to reflect the second occurrence, as shown in step 9.

What happens when there are no more characters to read?

The loop ends and the frequency map is complete, as shown in step 12 where no more characters remain.

Visual Quiz - 3 Questions

Look at the execution table, what is the frequency map after step 7?

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

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

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

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

💡 Hint

Check the 'Frequency Map State' column at step 7 in the execution table.

At which step does the count for character 'l' increase from 1 to 2?

A Step 7

B Step 9

C Step 8

D Step 10

💡 Hint

Look for the step where 'Increment 'l' count' happens in the 'Operation' column.

If the input string was empty, what would the frequency map be after execution?

A {}

B {'':1}

C nil

D {' ':1}

💡 Hint

Refer to the start and exit states in the execution table where no characters are processed.

Concept Snapshot

Character Frequency Counting:
- Use a map to store counts of each character.
- For each character in string:
  - If not in map, add with count 1.
  - Else, increment existing count.
- Result: map with character frequencies.

Full Transcript

This concept counts how many times each character appears in a string. We start with an empty map. For each character, we check if it is already in the map. If not, we add it with count 1. If yes, we increase its count by 1. We repeat this until all characters are processed. The final map shows the frequency of each character. For example, in the string 'hello', 'h' appears once, 'e' once, 'l' twice, and 'o' once.

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

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

2. Step 2: Compare with other options

   Length, first character, or position are different concepts, not frequency counting.

3. Final Answer:

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

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 Go code snippet correctly initializes a map to count character frequencies?

easy

A. freq := make(map[rune]int)

B. freq := map[int]string{}

C. freq := []int{}

D. freq := make([]rune, 0)

Solution

1. Step 1: Identify correct map initialization for character counts

   We need a map with keys as characters (rune) and values as counts (int), so make(map[rune]int) is correct.

2. Step 2: Check other options

   freq := map[int]string{} uses wrong types (int keys, string values), C and D are slices, not maps.

3. Final Answer:

   freq := make(map[rune]int) -> Option A

4. Quick Check:

   Map for rune to int = freq map [OK]

Hint: Use map[rune]int for char frequency in Go [OK]

Common Mistakes:

• Using slice instead of map
• Wrong key or value types in map
• Not using make() for map initialization

3. What is the output of this Go code?

package main
import "fmt"
func main() {
  s := "hello"
  freq := make(map[rune]int)
  for _, ch := range s {
    freq[ch]++
  }
  fmt.Println(freq['l'])
}

medium

A. 3

B. 1

C. 2

D. 0

Solution

1. Step 1: Count occurrences of 'l' in "hello"

   The string "hello" has 'l' twice (positions 2 and 3).

2. Step 2: Check map frequency for 'l'

   freq['l'] increments twice, so freq['l'] = 2.

3. Final Answer:

   2 -> Option C

4. Quick Check:

   Count of 'l' in "hello" = 2 [OK]

Hint: Count repeated chars carefully [OK]

Common Mistakes:

• Counting only once
• Confusing index with count
• Using wrong character in print

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

package main
import "fmt"
func main() {
  s := "test"
  freq := map[rune]int{}
  for i := 0; i < len(s); i++ {
    freq[s[i]] += 1
  }
  fmt.Println(freq)
}

medium

A. fmt.Println cannot print maps

B. Map freq is not initialized properly

C. Loop should use range instead of index

D. Using s[i] as byte instead of rune causes wrong map key type

Solution

1. Step 1: Check map key type and s[i] type

   Map keys are rune but s[i] is byte, causing type mismatch.

2. Step 2: Understand why this is an error

   Go does not automatically convert byte to rune for map keys, so this causes a compile error.

3. Final Answer:

   Using s[i] as byte instead of rune causes wrong map key type -> Option D

4. Quick Check:

   Byte vs rune key mismatch error [OK]

Hint: Use rune(s[i]) or range loop for correct key type [OK]

Common Mistakes:

• Ignoring byte vs rune difference
• Assuming map auto-converts keys
• Thinking map initialization is wrong

5. Given a string, how can you find the character with the highest frequency using Go maps?

hard

A. Use a slice to store counts and pick the last element

B. Count frequencies in a map, then iterate map to find max count character

C. Sort the string and pick the first character

D. Print the string length as the highest frequency

Solution

1. Step 1: Count character frequencies using a map

   Use a map[rune]int to count how many times each character appears.

2. Step 2: Iterate the map to find the character with the highest count

   Loop through the map keys and values, track the max count and corresponding character.

3. Final Answer:

   Count frequencies in a map, then iterate map to find max count character -> Option B

4. Quick Check:

   Map count + max search = highest frequency char [OK]

Hint: Use map to count, then find max by iteration [OK]

Common Mistakes:

• Sorting string does not give frequency
• Using slice without mapping chars
• Confusing length with frequency