Frequency Maps in Java: A Small Pattern with a Big Algorithmic Impact

Many algorithmic problems look unrelated at first.

Checking whether two words are anagrams, finding the most common event in a stream, deciding whether a palindrome can be built from a string, and detecting a permutation inside a sliding window all seem to require different solutions.

But they often share the same underlying question:

How many times does each value appear?

That question leads to one of the most useful patterns in data structures and algorithms: the frequency map.

In Java, frequency maps are a practical example of how choosing the right representation can simplify both the code and the reasoning behind an algorithm.

What Is a Frequency Map?

A frequency map associates each distinct value with the number of times it occurs.

For example, the word "banana" can be represented as:

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

The original sequence contains six letters, but the map captures its composition. It tells us which values are present and how often they appear while ignoring their positions.

That is what makes the pattern powerful. When order is irrelevant but quantity matters, a frequency map can turn a complicated comparison into a simple map operation.

Building a Frequency Map with HashMap

The most direct implementation uses a HashMap and getOrDefault:

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

static Map<Character, Integer> frequencyMap(String input) {
    Map<Character, Integer> frequencies = new HashMap<>();

    for (char character : input.toCharArray()) {
        int currentCount = frequencies.getOrDefault(character, 0);
        frequencies.put(character, currentCount + 1);
    }

    return frequencies;
}

For each character, the algorithm reads the current count, uses zero when the character is not yet present, and writes the incremented value back to the map.

Java also offers a more concise operation for this exact situation: Map.merge.

static Map<Character, Integer> frequencyMap(String input) {
    Map<Character, Integer> frequencies = new HashMap<>();

    for (char character : input.toCharArray()) {
        frequencies.merge(character, 1, Integer::sum);
    }

    return frequencies;
}

The expression has two behaviors:

1. If the key is absent, insert it with the value 1.
2. If the key is present, combine its current value with 1 using Integer::sum.

This is more than a shorter spelling of the same loop. It expresses the actual intent of the operation: merge one more occurrence into the current count.

Anagrams Become Map Equality

Two strings are anagrams when they contain exactly the same symbols with exactly the same frequencies.

Once both inputs have been normalized and converted into frequency maps, Java's Map.equals contract does the remaining work:

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

final class Anagrams {
    static boolean areAnagrams(String left, String right) {
        return frequencyMap(left).equals(frequencyMap(right));
    }

    private static Map<Integer, Integer> frequencyMap(String value) {
        Map<Integer, Integer> frequencies = new HashMap<>();

        value.toLowerCase(Locale.ROOT)
            .codePoints()
            .filter(codePoint -> !Character.isWhitespace(codePoint))
            .forEach(codePoint ->
                frequencies.merge(codePoint, 1, Integer::sum)
            );

        return frequencies;
    }
}

Examples:

Anagrams.areAnagrams("BANANA", "AAANNB");
// true

Anagrams.areAnagrams("Java", "Kotlin");
// false

The important part is not the final equality check. It is the representation that makes such a simple check possible.

This implementation also makes its normalization rules explicit: letter case and whitespace do not matter. In a real application, you still need to decide how punctuation, diacritics, and locale-specific case conversion should behave. A correct data structure cannot compensate for ambiguous input rules.

char Is Not Always a Complete Character

The first implementation uses char, which is often acceptable for ASCII-based interview problems. However, a Java char represents one UTF-16 code unit, not necessarily one complete Unicode symbol.

Some symbols require a surrogate pair and therefore occupy two char values. That is why the anagram implementation uses String.codePoints() and stores integer code points instead:

Map<Integer, Integer> frequencies = new HashMap<>();

input.codePoints().forEach(codePoint ->
    frequencies.merge(codePoint, 1, Integer::sum)
);

Code points still do not model every user-perceived grapheme cluster, but they avoid splitting supplementary Unicode characters into unrelated halves. For constrained algorithm exercises, state the ASCII assumption and use the simpler representation. For production text, choose the representation based on the actual domain.

Complexity

If an input contains n elements, building its frequency map takes O(n) expected time. The algorithm visits every element once, and HashMap lookup and update operations are expected to be constant time.

The map requires O(k) additional space, where k is the number of distinct values. In the worst case, every input value is unique and k = n.

For two strings of lengths n and m, the complete anagram check takes O(n + m) expected time. A sorting-based solution typically takes O(n log n + m log m) time.

Sorting may still be a good choice when it produces simpler code or memory constraints favor it. The goal is not to memorize one universal solution, but to recognize the available trade-offs.

When an Array Is Better Than a HashMap

A frequency map describes the idea, but a hash map is not always the best implementation.

If the domain is small and fixed, such as the 26 lowercase English letters, an array is simpler and avoids hashing and boxing:

static int[] letterFrequencies(String input) {
    int[] frequencies = new int[26];

    for (char character : input.toCharArray()) {
        frequencies[character - 'a']++;
    }

    return frequencies;
}

Use an array when values map cleanly to a compact numeric range. Use a HashMap when the set of possible keys is sparse, large, dynamic, or not naturally represented by small integer indexes.

This distinction often matters in interviews. Identifying the general frequency-map pattern is the first step; selecting the most appropriate concrete data structure is the second.

Beyond Anagrams

The same pattern appears in many problems:

• Palindrome construction: a sequence can be rearranged into a palindrome when at most one value has an odd frequency.
• Compression: repeated values can be represented as value-count pairs.
• Inventory and event aggregation: occurrences can be grouped by product, event type, status, or user.
• Duplicate detection: any count greater than one reveals repetition.
• Cryptanalysis: symbol distributions can expose patterns in encoded text.
• Sliding windows: a frequency map can track what enters and leaves a moving range.

Sliding windows are especially powerful when combined with frequency maps. Instead of rebuilding the map for every substring, update it incrementally:

frequencies.merge(entering, 1, Integer::sum);

frequencies.computeIfPresent(leaving, (key, count) ->
    count == 1 ? null : count - 1
);

In a map remapping function, returning null removes the entry. The code therefore increments the value entering the window and either decrements or removes the value leaving it.

This combination often turns a brute-force quadratic solution into a linear one.

A Small Pattern That Changes How You See Problems

Frequency maps are simple. Their value comes from recognizing when a problem is about identity and quantity rather than position.

Java gives us several ways to express that idea: explicit get and put operations, getOrDefault, merge, stream-based processing, or a fixed-size array. The best choice depends on the domain and on which version communicates the algorithm most clearly.

The next time a problem asks whether two collections contain the same values, which value appears most often, or whether a moving range satisfies a constraint, ask one question first:

Would counting the elements make the structure of this problem visible?

Very often, the map is not just an implementation detail. It is the idea that unlocks the solution.