Backend interview prep

Start Learning

Character Frequency

Java coding interview problem for Character Problems: Character Frequency.

Counting the frequency of characters is one of the most fundamental String interview problems.

Although it looks simple, this problem introduces several important concepts used throughout Data Structures and Algorithms.

It helps you understand:

  • HashMap
  • Arrays
  • ASCII
  • Unicode
  • String Traversal
  • Counting Algorithms
  • Time Complexity

Many advanced interview problems are based on character frequency, including:

  • Valid Anagram
  • First Non-Repeating Character
  • First Repeating Character
  • Group Anagrams
  • String Compression
  • Minimum Window Substring

Understanding this problem makes many interview questions much easier.

Problem Statement

Given a string,

count how many times each character appears.

Example 1

Input

banana

Output

b → 1

a → 3

n → 2

Example 2

Input

programming

Output

p → 1

r → 2

o → 1

g → 2

a → 1

m → 2

i → 1

n → 1

Example 3

Input

hello world

Output

h → 1

e → 1

l → 3

o → 2

(space) → 1

w → 1

r → 1

d → 1

What is Character Frequency?

Character frequency simply means

How many times each character occurs inside a string.

Example

apple

Frequency

a → 1

p → 2

l → 1

e → 1

Another Example

mississippi

Frequency

m → 1

i → 4

s → 4

p → 2

Why is this Question Asked in Interviews?

Interviewers use this problem to evaluate your understanding of:

  • HashMap
  • Arrays
  • Collections Framework
  • Iteration
  • Frequency Counting
  • Time Complexity

It is also the foundation for dozens of advanced interview questions.

Real-World Applications

Frequency counting is used everywhere.

Text Analytics

Count letters and words.

Search Engines

Analyze search keyword frequencies.

Data Compression

Run-Length Encoding uses frequencies.

Natural Language Processing (NLP)

Count character and word occurrences.

Cyber Security

Analyze repeated patterns in passwords and logs.

Bioinformatics

Count DNA sequence frequencies.

Understanding Frequency Counting

Suppose we have

banana

Read one character at a time.

Initially

{}

Read

b

Store

b → 1

Read

a

Now

b → 1

a → 1

Read

n

Now

b → 1

a → 1

n → 1

Read

a

Already exists.

Increase count.

a → 2

Continue until the end.

Final

b → 1

a → 3

n → 2

Frequency Table Visualization

Input

banana
Character Count
b 1
a 3
n 2

Another Example

Input

apple
Character Count
a 1
p 2
l 1
e 1

Mathematical Concept

Frequency can be represented as

Frequency(Character)

=

Number of Occurrences

For every character

Frequency

=

Previous Count

+

1

Example

banana

a

↓

1

↓

2

↓

3

ASCII Visualization

Input

code

Traversal

c

↓

Count = 1

o

↓

Count = 1

d

↓

Count = 1

e

↓

Count = 1

Input

google

Traversal

g

↓

1

o

↓

1

o

↓

2

g

↓

2

Dry Run

Input

banana

Current Map

{}

Read

b

{b=1}

Read

a

{b=1,a=1}

Read

n

{b=1,a=1,n=1}

Read

a

{b=1,a=2,n=1}

Read

n

{b=1,a=2,n=2}

Read

a

{b=1,a=3,n=2}

Approach 1 — Using HashMap (Recommended)

This is the most common interview solution.

The idea is simple.

  • Traverse the string.
  • Store every character in a HashMap.
  • Increment its frequency whenever it appears again.

Why HashMap?

HashMap provides nearly constant-time insertion and lookup.

Example

banana

HashMap

b → 1

a → 3

n → 2

Algorithm

  1. Create a HashMap.
  2. Traverse every character.
  3. Check if the character already exists.
  4. Increment its frequency.
  5. Print the map.

Java Program

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

public class CharacterFrequencyHashMap {

    public static void countFrequency(String text) {

        Map<Character, Integer> map =
                new HashMap<>();

        for (char ch : text.toCharArray()) {

            map.put(ch,
                    map.getOrDefault(ch, 0) + 1);

        }

        for (Map.Entry<Character, Integer> entry
                : map.entrySet()) {

            System.out.println(
                    entry.getKey() +
                    " -> " +
                    entry.getValue());

        }

    }

    public static void main(String[] args) {

        countFrequency("banana");

    }

}

Output

b -> 1

a -> 3

n -> 2

Step-by-Step Code Explanation

Create the HashMap.

Map<Character, Integer> map =
        new HashMap<>();

Traverse the string.

for(char ch : text.toCharArray())

Update frequency.

map.put(ch,
        map.getOrDefault(ch,0)+1);

Example

banana

Processing

b → 1

a → 1

n → 1

a → 2

n → 2

a → 3

Print the result.

for(Map.Entry<Character,Integer> entry
        : map.entrySet())

Dry Run of HashMap Approach

Input

apple
Character HashMap
a {a=1}
p {a=1,p=1}
p {a=1,p=2}
l {a=1,p=2,l=1}
e {a=1,p=2,l=1,e=1}

Advantages

  • Easy to understand.
  • Most common interview solution.
  • Supports Unicode characters.
  • Dynamic size.
  • Linear time complexity.

Drawbacks

  • Additional memory required.
  • Output order is not guaranteed.

Approach 2 — Using Frequency Array (ASCII)

If the input contains only ASCII characters,

using an array is faster than a HashMap.

Each character value acts as the array index.

Visualization

Input

banana

ASCII Array

Index('a') = 97

↓

3

Index('b') = 98

↓

1

Index('n') = 110

↓

2

Algorithm

  1. Create an integer array of size 256.
  2. Traverse the string.
  3. Increment frequency.
  4. Traverse the array.
  5. Print non-zero values.

Java Program

public class CharacterFrequencyArray {

    public static void countFrequency(String text) {

        int[] frequency =
                new int[256];

        for (char ch : text.toCharArray()) {

            frequency[ch]++;

        }

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

            if (frequency[i] > 0) {

                System.out.println(
                        (char) i +
                        " -> " +
                        frequency[i]);

            }

        }

    }

    public static void main(String[] args) {

        countFrequency("banana");

    }

}

Output

a -> 3

b -> 1

n -> 2

Step-by-Step Code Explanation

Create array.

int[] frequency =
        new int[256];

Each position represents one ASCII character.

Update frequency.

frequency[ch]++;

Print values.

if(frequency[i] > 0)

Display

Character

↓

Frequency

Time & Space Complexity

Approach Time Extra Space
HashMap O(n) O(k)
Frequency Array O(n) O(1)*

Where:

  • n = Length of the string
  • k = Number of distinct characters

*For a fixed ASCII character set, the array size is constant (256), so the extra space is considered O(1).

Comparison of Approaches

Feature HashMap Frequency Array
Interview Friendly ⭐⭐⭐⭐⭐ ⭐⭐⭐⭐⭐
Easy to Understand ⭐⭐⭐⭐⭐ ⭐⭐⭐⭐
Performance ⭐⭐⭐⭐ ⭐⭐⭐⭐⭐
Supports Unicode ⭐⭐⭐⭐⭐ Limited (ASCII example)

Advantages

  • Both approaches have O(n) time complexity.
  • HashMap supports dynamic character sets and Unicode.
  • Frequency Array is extremely fast for ASCII strings.
  • Both are widely accepted interview solutions.

Drawbacks

  • HashMap uses additional memory.
  • Frequency Array is limited to fixed-size character sets unless adapted.
  • HashMap does not preserve insertion order.

In Part 2, we'll cover:

  • Approach 3 – Using LinkedHashMap (Maintain Insertion Order)
  • Approach 4 – Using Java Streams
  • Approach 5 – Using TreeMap (Sorted Output)
  • Unicode Considerations
  • Comparison of All Approaches
  • Common Interview Mistakes
  • Edge Cases
  • Interview Follow-up Questions
  • Related Problems
  • Key Takeaways
  • Frequently Asked Interview Questions
  • Interview Tips

Approach 3 — Using LinkedHashMap (Maintain Insertion Order)

A LinkedHashMap is an extension of HashMap that preserves the order in which keys are inserted.

This is useful when the output must appear in the same order as the original string.

Why LinkedHashMap?

Example

banana

Insertion Order

b

a

n

Output

b -> 1

a -> 3

n -> 2

Unlike HashMap, the order is preserved.

Algorithm

  1. Create a LinkedHashMap.
  2. Traverse the string.
  3. Update character frequency.
  4. Print the map.

Java Program

import java.util.LinkedHashMap;
import java.util.Map;

public class CharacterFrequencyLinkedHashMap {

    public static void countFrequency(String text) {

        Map<Character, Integer> map =
                new LinkedHashMap<>();

        for (char ch : text.toCharArray()) {

            map.put(ch,
                    map.getOrDefault(ch, 0) + 1);

        }

        for (Map.Entry<Character, Integer> entry
                : map.entrySet()) {

            System.out.println(
                    entry.getKey() +
                    " -> " +
                    entry.getValue());

        }

    }

    public static void main(String[] args) {

        countFrequency("banana");

    }

}

Output

b -> 1

a -> 3

n -> 2

Advantages

  • Preserves insertion order.
  • Easy to understand.
  • Excellent interview solution.

Drawbacks

  • Slightly slower than HashMap.
  • Uses additional memory.

Approach 4 — Using Java Streams

Java 8 Streams provide a concise functional programming solution.

Instead of manually iterating,

Streams group characters and count their occurrences.

Algorithm

  1. Convert the string into a character stream.
  2. Group characters.
  3. Count each occurrence.
  4. Print the result.

Java Program

import java.util.LinkedHashMap;
import java.util.Map;
import java.util.function.Function;
import java.util.stream.Collectors;

public class CharacterFrequencyStreams {

    public static void countFrequency(String text) {

        Map<Character, Long> frequency =
                text.chars()
                        .mapToObj(ch -> (char) ch)
                        .collect(Collectors.groupingBy(
                                Function.identity(),
                                LinkedHashMap::new,
                                Collectors.counting()));

        frequency.forEach(
                (key, value) ->
                        System.out.println(
                                key + " -> " + value));

    }

    public static void main(String[] args) {

        countFrequency("banana");

    }

}

Output

b -> 1

a -> 3

n -> 2

Advantages

  • Modern Java style.
  • Very concise.
  • Demonstrates Java Streams.

Drawbacks

  • More difficult for beginners.
  • Additional Stream overhead.
  • Not usually preferred during coding interviews.

Approach 5 — Using TreeMap (Sorted Output)

Sometimes interviewers ask for the output to be sorted alphabetically.

TreeMap automatically sorts keys.

Visualization

Input

banana

TreeMap

a -> 3

b -> 1

n -> 2

Notice

Keys are sorted alphabetically.

Algorithm

  1. Create TreeMap.
  2. Traverse string.
  3. Update frequency.
  4. Print TreeMap.

Java Program

import java.util.Map;
import java.util.TreeMap;

public class CharacterFrequencyTreeMap {

    public static void countFrequency(String text) {

        Map<Character, Integer> map =
                new TreeMap<>();

        for (char ch : text.toCharArray()) {

            map.put(ch,
                    map.getOrDefault(ch, 0) + 1);

        }

        for (Map.Entry<Character, Integer> entry
                : map.entrySet()) {

            System.out.println(
                    entry.getKey() +
                    " -> " +
                    entry.getValue());

        }

    }

    public static void main(String[] args) {

        countFrequency("banana");

    }

}

Output

a -> 3

b -> 1

n -> 2

Advantages

  • Automatically sorts output.
  • Useful for alphabetical reports.
  • No extra sorting required.

Drawbacks

  • Slower than HashMap.
  • Tree operations take O(log k).

Unicode Considerations

Java String objects use UTF-16 encoding.

Examples

こんにちは

नमस्ते

😊😂😊

The following approaches support general Java strings:

  • HashMap
  • LinkedHashMap
  • TreeMap

For supplementary Unicode characters (such as many emoji), iterate over Unicode code points instead of individual char values.

Edge Cases

Input Expected Output
"" No Characters
"a" a → 1
"aaaa" a → 4
"AaAa" A → 2, a → 2 (case-sensitive)
" " (space) → 1
null Handle appropriately based on application requirements

Time & Space Complexity

Approach Time Extra Space
HashMap O(n) O(k)
Frequency Array O(n) O(1)*
LinkedHashMap O(n) O(k)
Java Streams O(n) O(k)
TreeMap O(n log k) O(k)

Where:

  • n = Length of the string
  • k = Number of distinct characters

*For a fixed ASCII character set, the array size is constant (256), so the extra space is considered O(1).

Comparison of All Approaches

Approach Interview Friendly Performance Maintains Order Sorted Output Best Use Case
HashMap ⭐⭐⭐⭐⭐ ⭐⭐⭐⭐⭐ ❌ ❌ General interviews
Frequency Array ⭐⭐⭐⭐⭐ ⭐⭐⭐⭐⭐ ❌ ❌ ASCII strings
LinkedHashMap ⭐⭐⭐⭐⭐ ⭐⭐⭐⭐ ✅ ❌ Maintain insertion order
Java Streams ⭐⭐⭐⭐ ⭐⭐⭐ ✅ ❌ Modern Java applications
TreeMap ⭐⭐⭐⭐ ⭐⭐⭐ ❌ ✅ Sorted reports

Common Interview Mistakes

Mistake 1

Using HashMap when insertion order is required.

Example

banana

Expected

b

a

n

Use LinkedHashMap.

Mistake 2

Using a Frequency Array for Unicode strings.

ASCII arrays work only for fixed-size character sets.

Mistake 3

Forgetting case sensitivity.

Example

A

a

These are different characters.

Mistake 4

Ignoring whitespace.

Input

hello world

The space is also a valid character.

Mistake 5

Using nested loops.

for(...)
    for(...)

This leads to

O(n²)

HashMap provides an

O(n)

solution.

Interview Follow-up Questions

Q1. Why is HashMap preferred?

Q2. When should LinkedHashMap be used?

Q3. Why is TreeMap slower?

Q4. Which solution is fastest?

Q5. How would you support Unicode?

Q6. Can this be solved without collections?

Q7. What if the output must be sorted?

Q8. How would you process billions of characters?

Q9. What is the difference between HashMap and LinkedHashMap?

Q10. What is the space complexity?

Related Problems

  • First Non-Repeating Character
  • First Repeating Character
  • Valid Anagram
  • Group Anagrams
  • Remove Duplicate Characters
  • String Compression
  • Longest Substring Without Repeating Characters
  • Minimum Window Substring

Key Takeaways

  • Character frequency counting is the foundation of many string interview problems.
  • HashMap is the most common interview solution because it is simple, flexible, and runs in O(n) time.
  • Frequency Array is the fastest option for ASCII input.
  • LinkedHashMap preserves insertion order, making it ideal when output order matters.
  • TreeMap automatically sorts characters alphabetically but has O(log k) insertion time.
  • Java Streams provide a concise functional programming alternative.

Frequently Asked Interview Questions

Q1. Which approach is best for interviews?

HashMap is the preferred interview solution because it is easy to explain, efficient, and supports all common character sets.

Q2. Which solution is fastest?

For ASCII input,

the Frequency Array approach is typically the fastest because array indexing is constant time.

Q3. When should I use LinkedHashMap?

Use LinkedHashMap when you must preserve the order in which characters first appear.

Example

banana

Output

b -> 1

a -> 3

n -> 2

Q4. When should I use TreeMap?

Use TreeMap when the output needs to be sorted alphabetically without calling an additional sorting method.

Q5. Does HashMap preserve order?

No.

HashMap does not guarantee insertion order.

Use LinkedHashMap for insertion order or TreeMap for sorted order.

Interview Tip

If an interviewer asks:

"Count the frequency of each character in a string."

Start with the HashMap solution because it is the industry-standard answer.

Then discuss progressively specialized approaches:

  1. HashMap (recommended)
  2. Frequency Array (ASCII optimization)
  3. LinkedHashMap (maintain insertion order)
  4. Java Streams (functional programming)
  5. TreeMap (sorted output)

Before coding, clarify requirements such as:

  • Is the input limited to ASCII or does it include Unicode?
  • Should uppercase and lowercase letters be treated differently?
  • Should spaces and punctuation be counted?
  • Does the output need to preserve insertion order or be sorted?

These questions demonstrate strong problem-solving skills and interview readiness while showing that you understand the trade-offs between different Java collection classes.