Premium

Character Counting

Basic Algorithms
≈ 2 min read

Frequencies turn a string into numbers

In many string problems, the position of every character is less important than how many times each character appears. Instead of searching repeatedly, we can traverse the string once and accumulate frequencies. If the alphabet is known in advance and small, a counter array is usually the simplest choice. 

String text = "banana";
int[] frequency = new int[26];

for (int i = 0; i < text.length(); i++) {
    char c = text.charAt(i);
    frequency[c - 'a']++;
}

int countA = frequency['a' - 'a']; // 3

Here each array index corresponds to one letter from 'a' to 'z'. Subtracting 'a' converts a letter into an index from 0 to 25. A single pass over the string takes O(n), while the array size does not depend on the input length.

When the alphabet is not known in advance

If the set of possible characters is wider or not predefined, allocating an array for one fixed range is inconvenient. In that case, frequencies can be stored in a HashMap only for characters that actually occur. 

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

for (int i = 0; i < text.length(); i++) {
    char c = text.charAt(i);
    frequency.merge(c, 1, Integer::sum);
}

This solution uses additional memory proportional to the number of distinct characters. On average, one full pass remains linear, while the code no longer depends on a particular alphabet.

What prepared frequencies give us

After counting, we can quickly answer questions about the composition of a string: whether repeated characters exist, which character appears most often, how many distinct characters are present, or whether the count of a particular letter matches between two data sets.

Choose the structure from the problem constraints. For guaranteed lowercase English letters, an array of 26 counters is simpler and more compact. For an unknown character set, an associative structure is more universal.
Back Next