Character Frequency Counting in DSA Java - Execution Trace

Concept Flow - Character Frequency Counting

Start with input string

↓

Initialize empty frequency map

↓

For each character in string

↓

Check if character in map?

No→Add character with count 1

Yes↓

Increment character count

↓

Repeat for all characters

↓

Return frequency map

We start with the input string, then for each character, we update its count in a frequency map until all characters are processed.

Execution Sample

DSA Java

String s = "hello";
Map<Character, Integer> freq = new HashMap<>();
for (char c : s.toCharArray()) {
  freq.put(c, freq.getOrDefault(c, 0) + 1);
}
System.out.println(freq);

This code counts how many times each character appears in the string "hello" and prints the frequency map.

Execution Table

Step	Operation	Character Processed	Frequency Map Before	Frequency Map After	Visual State
1	Initialize frequency map	N/A	{}	{}	{}
2	Process character	'h'	{}	{'h':1}	{'h':1}
3	Process character	'e'	{'h':1}	{'h':1, 'e':1}	{'h':1, 'e':1}
4	Process character	'l'	{'h':1, 'e':1}	{'h':1, 'e':1, 'l':1}	{'h':1, 'e':1, 'l':1}
5	Process character	'l'	{'h':1, 'e':1, 'l':1}	{'h':1, 'e':1, 'l':2}	{'h':1, 'e':1, 'l':2}
6	Process character	'o'	{'h':1, 'e':1, 'l':2}	{'h':1, 'e':1, 'l':2, 'o':1}	{'h':1, 'e':1, 'l':2, 'o':1}
7	End of string	N/A	{'h':1, 'e':1, 'l':2, 'o':1}	{'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 1	After 2	After 3	After 4	After 5	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}
current_char	N/A	'h'	'e'	'l'	'l'	'o'	N/A

Key Moments - 3 Insights

Why do we check if the character is already in the map before adding?

Because if the character is already in the map, we need to increase its count instead of starting from 1. This is shown in steps 4 and 5 where 'l' is processed twice, incrementing its count.

What happens if the input string is empty?

The loop does not run, so the frequency map remains empty as shown in step 1 and exit at step 7 with no changes.

Why do we use getOrDefault when updating the count?

getOrDefault returns the current count if the character exists, or 0 if it does not. This avoids errors and allows incrementing counts smoothly, as seen in all processing steps.

Visual Quiz - 3 Questions

Look at the execution table, what is the frequency map after processing the second character?

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

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

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

D {'h':1}

💡 Hint

Check row 3 in the execution_table under 'Frequency Map After'

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

A Step 4

B Step 5

C Step 3

D Step 6

💡 Hint

Look at the 'Character Processed' and 'Frequency Map After' columns in steps 4 and 5

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

A {}

B {' ':1}

C null

D {'h':1}

💡 Hint

Refer to the 'Frequency Map Before' and 'Frequency Map After' in step 1 and 7

Concept Snapshot

Character Frequency Counting:
- Use a map to store counts
- For each character, add or increment count
- Use getOrDefault to handle missing keys
- Result is a map of characters to their counts
- Useful for text analysis and counting duplicates

Full Transcript

This concept shows how to count how many times each character appears in a string. We start with an empty map. For each character in the string, 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 each character and how many times it appeared. This is useful for understanding text data and frequency analysis.

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