Count Character Occurrences - Build a Frequency Map - Java

Category: Medium | Concepts used: HashMap, frequency counting, array-based counting

---

Problem Statement

Given a string, build a map showing how many times each character appears.

Input : "apple"      Output: {a=1, p=2, l=1, e=1}

Examples (with edge scenarios)

#	Input	Output	Why
1	"apple"	{a=1, p=2, l=1, e=1}	'p' repeats twice
2	"" (empty)	{}	No characters, empty map
3	"aaa"	{a=3}	All same character
4	"Aa"	{A=1, a=1} (case-sensitive by default)	'A' and 'a' are different keys unless normalized
5	"a b" (with space)	{a=1, ' '=1, b=1}	The space itself is counted as a character too, unless excluded

Common Fresher Mistake

Mistake	What happens	Fix
Using map.get(ch) + 1 without checking if the key exists yet	NullPointerException on the first occurrence of any character (unboxing null)	Use getOrDefault(ch, 0) + 1, or check containsKey first
Assuming HashMap iteration order matches input order	HashMap doesn’t guarantee any particular order	Use LinkedHashMap if you need to preserve first-seen order

---

Before You Code: Clarify the Contract

Before choosing an algorithm, confirm how null and empty strings should behave, whether comparison is case-sensitive, and whether spaces or punctuation count. Java char values are UTF-16 code units, not always complete human-visible Unicode characters, so international text may require code points or grapheme-aware libraries.

Analogy: Sorting Candies in Boxes

Imagine you have a big bag of colored candies (the characters in the string) and a set of empty storage boxes:

• When you pick up a red candy, you look at your labels:
  • If you already have a box labeled “Red” (containsKey), you increment the number of candies on the box’s counter by 1.
  • If you don’t have a box labeled “Red” yet, you create a new box, write “Red” on it, set the counter to 1 (getOrDefault(ch, 0) + 1), and place it on the shelf.
• By the time you’ve sorted every candy, the labels and counters on the boxes tell you exactly how many candies of each color you have!

---

Solution 1 — Using HashMap with getOrDefault() (Recommended)

Intuition

For each character we encounter, we want to answer: “how many times have I seen this so far?” A HashMap<Character, Integer> is exactly built for this — the character is the key, the running count is the value. getOrDefault(ch, 0) handles the “first time seeing this character” case gracefully — treating an unseen character as starting from 0.

import java.util.HashMap;

public class CharFrequency {
    public static HashMap<Character, Integer> countChars(String str) {
        HashMap<Character, Integer> freq = new HashMap<>();

for (char ch : str.toCharArray()) {
            freq.put(ch, freq.getOrDefault(ch, 0) + 1);
        }
        return freq;
    }

public static void main(String[] args) {
        System.out.println(countChars("apple"));  // {a=1, p=2, l=1, e=1}
        System.out.println(countChars(""));         // {}
        System.out.println(countChars("aaa"));       // {a=3}
    }
}

Output:

{a=1, p=2, l=1, e=1}
{}
{a=3}

(Note: exact printed order from a plain HashMap isn’t guaranteed — see Solution 2 if order matters.)

Dry Run (str = “apple”)

freq = {}
'a' -> getOrDefault('a',0)=0 -> put('a', 1) -> freq={a=1}
'p' -> getOrDefault('p',0)=0 -> put('p', 1) -> freq={a=1,p=1}
'p' -> getOrDefault('p',0)=1 -> put('p', 2) -> freq={a=1,p=2}
'l' -> getOrDefault('l',0)=0 -> put('l', 1) -> freq={a=1,p=2,l=1}
'e' -> getOrDefault('e',0)=0 -> put('e', 1) -> freq={a=1,p=2,l=1,e=1}
Final: {a=1, p=2, l=1, e=1}

Interviewer’s take

This is the standard, expected solution — clean, O(n), and getOrDefault() is exactly the right tool to avoid the classic null-check headache. Interviewers are looking for fluency with HashMap here, a data structure that comes up constantly in real QA/automation work (e.g., counting log entries, test failures by category, etc.).

Follow-up questions you might get:

• “What if you need to preserve the order characters first appeared?” → Use LinkedHashMap instead of HashMap.
• “How would you find the most frequent character from this map?” → Iterate over the map’s entries and track the max value seen — a natural follow-up problem (see Q37).

---

Solution 2 — Using LinkedHashMap (Preserves Insertion Order)

Intuition

Same counting logic as Solution 1, but swapping the underlying map type preserves the order characters were first encountered — useful when you want the frequency map to read naturally in the order the string was scanned.

import java.util.LinkedHashMap;

public class CharFrequencyOrdered {
    public static LinkedHashMap<Character, Integer> countChars(String str) {
        LinkedHashMap<Character, Integer> freq = new LinkedHashMap<>();
        for (char ch : str.toCharArray()) {
            freq.put(ch, freq.getOrDefault(ch, 0) + 1);
        }
        return freq;
    }

public static void main(String[] args) {
        System.out.println(countChars("apple")); // {a=1, p=2, l=1, e=1} - guaranteed order
    }
}

Output:

{a=1, p=2, l=1, e=1}

Interviewer’s take

Great alternative if order matters for your use case (e.g., displaying results predictably in a report or UI). Costs a small amount of extra memory/performance compared to HashMap, which is worth mentioning if asked about trade-offs.

---

Solution 3 — Using an int[26] Array (Only for Lowercase Letters, Fastest)

Intuition

If we know the input only contains lowercase English letters, we don’t need a general-purpose HashMap at all — we can use a small fixed-size array where each index directly corresponds to one letter ('a'→index 0, 'b'→index 1, etc.), giving direct O(1) array access instead of hashing.

public class CharFrequencyArray {
    public static int[] countChars(String str) {
        int[] freq = new int[26]; // one slot per lowercase letter
        for (char ch : str.toCharArray()) {
            freq[ch - 'a']++; // 'a' maps to index 0, 'b' to 1, etc.
        }
        return freq;
    }

public static void main(String[] args) {
        int[] result = countChars("apple");
        System.out.println("a: " + result[0]); // a: 1
        System.out.println("p: " + result['p' - 'a']); // p: 2
    }
}

Output:

a: 1
p: 2

Interviewer’s take

This is a nice, performance-focused bonus — faster and more memory-efficient than a HashMap for a known, small character set, but it only works for lowercase English letters as written (would need adjustment or a bigger array for uppercase, digits, symbols, or Unicode). Mention this as an optimization when the input character set is known and limited.

---

📊 Visual Flowchart

graph TD
    Start["Input String S"] --> NullCheck{"S is null?"}
    NullCheck -->|Yes| RetNull["Return empty map"]
    NullCheck -->|No| InitMap["Initialize HashMap freq"]
    InitMap --> Loop{"i < S.length()?"}
    Loop -->|Yes| Fetch["ch = S.charAt(i)"]
    Fetch --> GetCount["count = freq.getOrDefault(ch, 0)"]
    GetCount --> PutMap["freq.put(ch, count + 1)"]
    PutMap --> IncLoop["i++"]
    IncLoop --> Loop
    Loop -->|No| End["Return freq"]

---

Final Verdict — Which Solution Should You Give?

• Solution 1 (HashMap + getOrDefault) is the expected default answer — works for any character set, general purpose.
• Mention Solution 2 if order matters.
• Mention Solution 3 as a performance bonus if the interviewer asks “can you do this without a HashMap” or “how would you optimize for known input constraints.”

---

Quick Recap

Approach	Time	Space	Works for any character?	Preserves order?
HashMap	O(n)	O(k) — k = distinct chars	Yes	No
LinkedHashMap	O(n)	O(k)	Yes	Yes
int[26] array	O(n)	O(1) — fixed size	Lowercase only	Yes (by index order)