Frequency Counting

Concept

Many string problems ask you to figure out “how many times does this character appear?” or “do these two strings have the exact same characters?”.
You solve these by building a Frequency Counter—a Hash Map that tallies the occurrences of each character.

Instead of writing $O(N^2)$ nested loops to compare characters, building a Frequency Counter takes exactly $O(N)$ time and provides $O(1)$ lookups.

Mental Model

String: "hello"

The Frequency Counter (Hash Map):

{
  "h": 1,
  "e": 1,
  "l": 2,
  "o": 1
}

Implementation

function buildFrequencyMap(s: string): Map<string, number> {
    const map = new Map<string, number>();
    
    for (let char of s) {
        // If it exists, add 1. If it doesn't, default to 0, then add 1.
        map.set(char, (map.get(char) || 0) + 1);
    }
    
    return map;
}

The Array Optimization (ASCII Map)

If you know the string only contains lowercase English letters (a-z), you do not need to use a heavy, slow Map or Javascript object.
You can use a Fixed-Size Array of 26 integers. This guarantees absolute $O(1)$ space and is blazingly fast because arrays don’t have to calculate memory hashes.

function buildAsciiArray(s: string): number[] {
    const counts = new Array(26).fill(0);
    
    for (let i = 0; i < s.length; i++) {
        // Find the relative index: 'a' becomes 0, 'b' becomes 1, 'z' becomes 25
        // charCodeAt(i) returns the ASCII number (e.g., 'a' is 97)
        const relativeIndex = s.charCodeAt(i) - 97;
        counts[relativeIndex]++;
    }
    
    return counts;
}

First Unique Character

Problem: Find the first non-repeating character in a string and return its index.

function firstUniqChar(s: string): number {
    // Pass 1: Build the map (O(N) time)
    const counts = new Map<string, number>();
    for (let char of s) {
        counts.set(char, (counts.get(char) || 0) + 1);
    }
    
    // Pass 2: Find the first one with a count of exactly 1 (O(N) time)
    for (let i = 0; i < s.length; i++) {
        if (counts.get(s[i]) === 1) {
            return i;
        }
    }
    
    return -1;
}

Interview Questions

Q: A candidate solves a string problem using a Map. The interviewer asks: “What is the Space Complexity of your Frequency Map?” The candidate says ”$O(N)$ because I have to store every character.” Are they correct?
A: This is a classic trick question.
If the string is 10 Billion characters long, the Map will not hold 10 Billion entries. If the string only contains lowercase English letters (a-z), the Map will have an absolute maximum size of 26 keys.
Because 26 is a constant ceiling, the Space Complexity is mathematically $O(1)$, not $O(N)$.
(However, if the string can contain any arbitrary Unicode character, the map could theoretically grow to 140,000 keys, but that is still technically a fixed constant ceiling, making it $O(1)$).

Q: When building a frequency map in JavaScript, is it better to use new Map() or a plain object {}?
A: new Map() is significantly better for algorithmic interviews.

1. Map guarantees iteration order (insertion order). Plain objects historically did not.
2. Map does not inherit prototype garbage (like toString), so you won’t accidentally hit bugs if the string contains a word like “constructor”.
3. Map has a built-in .size property. To get the size of an object, you have to run an $O(K)$ Object.keys(obj).length scan.