Character Frequency Counting in DSA Go

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 right jar each time you see it.

input string: h e l l o
frequency map: {}

Dry Run Walkthrough

Input: string: "hello"

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

Step 1: Look at first character 'h' and add it to the map with count 1

{'h': 1}

Why: We start counting characters from the beginning

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

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

Why: Add new character to the map with count 1

Step 3: Look at third character 'l' and add it to the map with count 1

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

Why: Add new character to the map with count 1

Step 4: Look at fourth character 'l' and increase its count to 2

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

Why: Character 'l' seen again, increase count

Step 5: Look at fifth character 'o' and add it to the map with count 1

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

Why: Add new character to the map with count 1

Result:

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

Annotated Code

DSA Go

package main

import (
	"fmt"
)

func charFrequency(s string) map[rune]int {
	freq := make(map[rune]int)
	for _, ch := range s {
		freq[ch]++ // increase count for character ch
	}
	return freq
}

func main() {
	input := "hello"
	result := charFrequency(input)
	for ch, count := range result {
		fmt.Printf("'%c': %d\n", ch, count)
	}
}

for _, ch := range s {

iterate over each character in the string

freq[ch]++ // increase count for character ch

increment count for current character in frequency map

Output

'h': 1

'e': 1

'l': 2

'o': 1

Complexity Analysis

Time: O(n) because we look at each character once in the 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 frequency map is faster and simpler than nested loops that count each character separately, which would be O(n^2)

Edge Cases

empty string

returns an empty map with no characters

DSA Go

for _, ch := range s {

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

returns map with one character and count equal to string length

DSA Go

freq[ch]++ // increase count for character ch

string with spaces and punctuation, e.g. "hi! hi!"

counts spaces and punctuation as characters too

DSA Go

freq[ch]++ // increase count for character ch

When to Use This Pattern

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

Common Mistakes

Mistake: Trying to count characters by nested loops causing slow performance
Fix: Use a map to count characters in one pass instead of nested loops

Mistake: Not handling empty strings causing errors
Fix: Ensure loop handles empty input gracefully by design

Summary

Counts how many times each character appears in a string.

Use when you need to know frequency of characters quickly and simply.

The key is to update counts in a map as you scan the string 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