Character Frequency Counting in DSA Java

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: {h:0, e:0, l:0, o:0}

Dry Run Walkthrough

Input: word: "hello"

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

Step 1: Look at first character 'h', add 1 to 'h' count

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

Why: We start counting from the first letter

Step 2: Look at second character 'e', add 1 to 'e' count

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

Why: Count each new letter as we see it

Step 3: Look at third character 'l', add 1 to 'l' count

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

Why: Add count for 'l' the first time

Step 4: Look at fourth character 'l', add 1 more to 'l' count

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

Why: Increase count for repeated letter

Step 5: Look at fifth character 'o', add 1 to 'o' count

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

Why: Count last letter

Result:

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

Annotated Code

DSA Java

import java.util.HashMap;
import java.util.Map;

public class CharacterFrequency {

    public static Map<Character, Integer> countFrequency(String word) {
        Map<Character, Integer> freqMap = new HashMap<>();
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            freqMap.put(c, freqMap.getOrDefault(c, 0) + 1); // add or update count
        }
        return freqMap;
    }

    public static void main(String[] args) {
        String input = "hello";
        Map<Character, Integer> result = countFrequency(input);
        for (Map.Entry<Character, Integer> entry : result.entrySet()) {
            System.out.println(entry.getKey() + ": " + entry.getValue());
        }
    }
}

freqMap.put(c, freqMap.getOrDefault(c, 0) + 1); // add or update count

increment count for current character or start at 1 if not seen

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 because we store counts for each

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

Edge Cases

empty string

returns empty frequency map

DSA Java

for (int i = 0; i < word.length(); i++) {

string with all same characters

count equals string length for that character

DSA Java

freqMap.put(c, freqMap.getOrDefault(c, 0) + 1);

string with special characters or spaces

counts them as normal characters

DSA Java

char c = word.charAt(i);

When to Use This Pattern

When you need to count how many times items appear in a collection, use a frequency map to track counts efficiently.

Common Mistakes

Mistake: Not initializing count to 0 before adding 1 causes errors
Fix: Use getOrDefault to handle missing keys by starting count at 0

Summary

Counts how many times each character appears in a string.

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

Keep a map and update counts as you scan each character once.

Practice

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

easy

A. The first character of the string

B. The length of the string

C. How many times each character appears in the string

D. The position of a character in the string

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: Identify what frequency counting returns

   It returns a count for each character, not the length or position.

3. Final Answer:

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

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 frequency gives character positions
• Assuming frequency returns only unique characters

2. Which Java data structure is best suited to store character frequencies for a string?

easy

A. HashMap

B. ArrayList<Character>

C. LinkedList<Integer>

D. Stack<Character>

Solution

1. Step 1: Identify data structure needs

   We need to map each character to its count, so a key-value pair structure is needed.

2. Step 2: Choose the correct Java collection

   HashMap stores characters as keys and their counts as values.

3. Final Answer:

   HashMap -> Option A

4. Quick Check:

   Map characters to counts = HashMap [OK]

Hint: Use HashMap to map characters to their counts [OK]

Common Mistakes:

• Using ArrayList which doesn't map keys to values
• Choosing LinkedList which is a list, not a map
• Using Stack which is for LIFO, not frequency counting

3. What is the output of the following Java code?

String s = "hello";
Map freq = new HashMap<>();
for (char c : s.toCharArray()) {
  freq.put(c, freq.getOrDefault(c, 0) + 1);
}
System.out.println(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. Compilation error

Solution

1. Step 1: Count characters in "hello"

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

2. Step 2: Check code logic for counting

   Code uses getOrDefault to add 1 to existing count or start at 0, correctly counting frequencies.

3. Final Answer:

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

4. Quick Check:

   Count 'l' twice, others once = {h=1, e=1, l=2, o=1} [OK]

Hint: Count each character carefully, watch repeated letters [OK]

Common Mistakes:

• Counting 'l' only once
• Confusing getOrDefault usage
• Expecting syntax error incorrectly

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

String s = "test";
Map freq = new HashMap<>();
for (int i = 0; i <= s.length(); i++) {
  char c = s.charAt(i);
  freq.put(c, freq.getOrDefault(c, 0) + 1);
}

medium

A. Using <= in loop causes IndexOutOfBoundsException

B. HashMap cannot store Character keys

C. getOrDefault method is not available in HashMap

D. charAt method does not exist for String

Solution

1. Step 1: Analyze loop condition

   Loop uses i <= s.length(), but valid indices are 0 to s.length()-1.

2. Step 2: Identify error consequence

   Accessing s.charAt(s.length()) causes IndexOutOfBoundsException at runtime.

3. Final Answer:

   Using <= in loop causes IndexOutOfBoundsException -> Option A

4. Quick Check:

   Loop index must be less than length [OK]

Hint: Loop index must be less than string length, not equal [OK]

Common Mistakes:

• Thinking HashMap can't store Character keys
• Assuming getOrDefault is unavailable
• Believing charAt doesn't exist for String

5. Given a string with mixed case letters, how can you count character frequencies ignoring case (treat 'A' and 'a' as same)? Choose the best approach.

hard

A. Ignore characters that are uppercase

B. Count uppercase and lowercase separately and add later

C. Use a TreeMap instead of HashMap

D. Convert string to lowercase before counting frequencies

Solution

1. Step 1: Understand case-insensitive counting

   To treat 'A' and 'a' the same, convert all characters to one case.

2. Step 2: Choose best method

   Converting entire string to lowercase before counting ensures all letters are uniform.

3. Final Answer:

   Convert string to lowercase before counting frequencies -> Option D

4. Quick Check:

   Uniform case simplifies frequency counting [OK]

Hint: Convert string to one case before counting [OK]

Common Mistakes:

• Counting uppercase and lowercase separately
• Using TreeMap which doesn't solve case issue
• Ignoring uppercase letters incorrectly