Character Frequency Counter — Problem Statement & Solution Guide
Problem Description
Given a string composed exclusively of lowercase English letters, implement a function that returns a mapping of each distinct character to the number of times it appears in the string. The function must accept a single argument of type string; if the argument is not a string, it should raise a TypeError. The output should be a dictionary (or object) where keys are characters and values are non‑negative integers representing their frequencies. The order of keys in the output does not matter.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Character Frequency Counter"
WHY DOES IT MATTER?
The hash-map counting pattern transforms a potentially quadratic problem into linear time, which is critical for scalability. It eliminates redundant scans and leverages constant-time data structure operations, making it a go-to technique for any problem involving frequency analysis.
OPTIMIZATION CHALLENGE
The key insight is to perform a single pass over the data while maintaining a mutable count for each unique key, thereby avoiding nested loops and repeated lookups.
REAL-WORLD CONNECTION
In log aggregation services, each log entry is parsed and its type counted to generate metrics. Using a hash map allows the system to process millions of logs in real time, similar to how the algorithm counts characters in a string.
When explaining this pattern, emphasize the trade-off between time and space: you pay a small, bounded space cost (at most 26 entries) to gain linear time, which is often the most valuable optimization in interview settings.
COMPLEXITY AT A GLANCE
O(n)O(1)Core Theory — Why This Approach?
The fundamental task is to map each distinct character in a string to its frequency count. A naive approach would iterate over the string for every character, performing a linear scan to count occurrences, resulting in an O(n^2) time complexity where n is the string length. This becomes infeasible for large inputs because the number of comparisons grows quadratically. The optimal paradigm leverages a hash map (or dictionary) to store counts: iterate through the string once, incrementing the count for each character in constant average time. This reduces the time complexity to O(n) while keeping space usage bounded by the number of unique characters, which for lowercase English letters is at most 26, i.e., O(1) auxiliary space.
The algorithmic theory behind this pattern is rooted in the concept of linear-time counting via associative arrays. By treating each character as a key, we avoid repeated scans and exploit the constant-time lookup and update properties of hash tables. This pattern is a cornerstone in many string-processing problems such as anagram detection, palindrome checks, and frequency-based sorting, where the bottleneck is often the repeated counting of elements.
In distributed systems, this approach mirrors the MapReduce paradigm: the map phase emits key-value pairs (character, 1) for each occurrence, and the reduce phase aggregates counts per key. Understanding this parallelism helps engineers design scalable solutions for massive text corpora, reinforcing why the hash-map counting pattern is both theoretically optimal and practically indispensable.
Interview Questions on This Problem
Q1How would you modify the character frequency counter to handle Unicode strings that may contain characters beyond the ASCII range?
Use a hash map that accepts Unicode keys; in languages like Python, a dictionary naturally handles Unicode. Ensure the input validation checks for string type, not just ASCII, and consider normalizing the string (e.g., NFC) if case folding or accent removal is required. The algorithmic complexity remains O(n) with space proportional to the number of unique Unicode code points present.
Q2A fintech platform needs to detect the most frequent transaction type in a log of 10 million entries. Which data structure would you recommend and why?
A hash map (or dictionary) mapping transaction type identifiers to counts is ideal because it offers O(1) average insertion and lookup. After populating the map in a single pass (O(n)), you can iterate over the entries to find the maximum count, yielding an overall O(n) solution suitable for high-throughput logs.
Q3During a coding interview at a high-growth startup, the interviewer asks you to optimize the space usage of the frequency counter. What strategy would you propose?
Since the input alphabet is known to be lowercase English letters, you can replace the hash map with a fixed-size array of length 26, indexed by the character's ordinal offset. This reduces space to O(1) and can improve cache locality, making the solution faster in practice.
Examples
Input
"abac"
Output
{"a":2,"b":1,"c":1}Explanation: Count each character: a appears twice, b once, c once. The resulting dictionary maps each character to its count.
Input
"zzzzzz"
Output
{"z":6}Explanation: The string contains six 'z' characters and no others, so the dictionary contains a single entry with key 'z' and value 6.
Input
"hello"
Output
{"h":1,"e":1,"l":2,"o":1}Explanation: Traverse the string: h→1, e→1, l→2 (two occurrences), o→1. The dictionary reflects these counts.
Constraints
- 1 <= len(s) <= 100000
- s contains only characters from 'a' to 'z'
- function must raise TypeError for non-string inputs
Optimal Approach & Strategy
Traverse the string once, updating a hash map that stores counts for each character. This achieves O(n) time and O(1) space for a fixed alphabet.
Brute Force Approach
Check each character against every other character in the string, incrementing a counter when matches are found. This results in a nested loop and O(n^2) time complexity.
Verified Code Solutions
/**
* @param {string} s
* @return {Object}
*/
function countCharacters(s) {
if (typeof s !== 'string') {
throw new TypeError("Input must be a string");
}
const freq = {};
for (const char of s) {
freq[char] = (freq[char] || 0) + 1;
}
return freq;
}
// Example usage
// console.log(countCharacters("abac"));#include <iostream>
#include <string>
#include <unordered_map>
#include <stdexcept>
std::unordered_map<char, int> countCharacters(const std::string& s) {
std::unordered_map<char, int> freq;
for (char c : s) {
freq[c]++;
}
return freq;
}
int main() {
std::string input;
std::cin >> input;
auto result = countCharacters(input);
for (const auto& pair : result) {
std::cout << pair.first << ":" << pair.second << " ";
}
std::cout << std::endl;
return 0;
}import java.util.HashMap;
import java.util.Map;
public class Solution {
public Map<Character, Integer> countCharacters(String s) {
if (s == null) {
throw new IllegalArgumentException("Input must not be null");
}
Map<Character, Integer> freq = new HashMap<>();
for (char c : s.toCharArray()) {
freq.put(c, freq.getOrDefault(c, 0) + 1);
}
return freq;
}
public static void main(String[] args) {
Solution sol = new Solution();
System.out.println(sol.countCharacters("abac"));
}
}def count_characters(s):
if not isinstance(s, str):
raise TypeError("Input must be a string")
freq = {}
for char in s:
freq[char] = freq.get(char, 0) + 1
return freq
# Example usage
# print(count_characters("abac"))/**
* @param {string} s
* @return {Object}
*/
function countCharacters(s) {
if (typeof s !== 'string') {
throw new TypeError("Input must be a string");
}
const freq = {};
for (const char of s) {
freq[char] = (freq[char] || 0) + 1;
}
return freq;
}
// Example usage
// console.log(countCharacters("abac"));Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.