04. Find the Frequency of Each Character

Difficulty:EasyPattern:Hash Map Frequency CountingTime:O(n)Space:O(k)

Construct a frequency table mapping each character in a string to its total number of occurrences.

How It Works & Algorithmic Design

This relies on Hash Map Frequency Counting:

Hash Map Setup: Initialize an empty key-value Hash Map freqMap.
Character Scanning: Iterate through each character ch in the string.
Map Update:
- If ch exists as a key in freqMap, increment its associated value (freqMap[ch] + 1).
- If ch is not in freqMap, insert it with an initial value of 1 (freqMap[ch] = 1).
Result: Return the populated frequency map.

Why This Approach Works Best

Hash Map insertions and lookups take $O(1)$ average time. Scanning the string of length $n$ takes $O(n)$ time. The space complexity is $O(k)$, where $k$ is the number of unique characters in the alphabet (at most $O(1)$ for fixed character sets like ASCII or lowercase English letters).

Example Walkthrough

Input String: "banana"

6-character string with repeating letters.

Step-by-Step Map Updates: 'b': 1 -> 'a': 1 -> 'n': 1 -> 'a': 2 -> 'n': 2 -> 'a': 3

Updates key counts as characters are scanned.

Output Frequency Table: { 'b': 1, 'a': 3, 'n': 2 }

Final counts for each unique character.

Answer: Build character frequency table

function charFrequency(s) {
  const freq = {};
  for (const ch of s) {
    freq[ch] = (freq[ch] || 0) + 1;
  }
  return freq;
}

💡 Populate a Hash Map by using characters as keys and their counts as values.

Key Takeaways

Hash Maps provide average $O(1)$ insertion and lookup times for frequency counting.
Frequency maps serve as building blocks for solving complex string problems like Anagram Detection.
Time complexity is $O(n)$, and space complexity is bounded by the size of the unique character set ($O(k)$).