Character Frequency Maps

Overview

Character frequency maps (also called character counting or frequency counting) are fundamental to many string algorithms. By tracking how many times each character appears in a string, you can solve problems involving anagrams, palindromes, character validation, and more.

The technique involves creating a data structure (array, Map, or object) that maps each character to its count. This simple idea unlocks efficient solutions to a wide variety of string problems.

Data Structures for Frequency Counting

Option 1: Array (Fixed Alphabet)

For lowercase letters (a-z), use an array of size 26. For ASCII, use size 128 or 256.

function countFrequencyArray(s: string): number[] {
  const freq = new Array(26).fill(0);
  for (const char of s) {
    freq[char.charCodeAt(0) - 'a'.charCodeAt(0)]++;
  }
  return freq;
}

Advantages: O(1) access, memory efficient for fixed alphabets

Use when: You know the alphabet size is small and fixed (e.g., lowercase letters)

Option 2: Map/Object (Dynamic)

Use a Map or object when the alphabet is unknown or large.

function countFrequencyMap(s: string): Map<string, number> {
  const freq = new Map<string, number>();
  for (const char of s) {
    freq.set(char, (freq.get(char) || 0) + 1);
  }
  return freq;
}

Advantages: Works for any characters, Unicode-friendly

Use when: Alphabet size is unknown or characters are arbitrary

Common Patterns

Pattern 1: Anagram Detection

Two strings are anagrams if they have the same character frequencies.

function isAnagram(s: string, t: string): boolean {
  if (s.length !== t.length) return false;
  
  const freq = new Map<string, number>();
  
  // Count characters in s
  for (const char of s) {
    freq.set(char, (freq.get(char) || 0) + 1);
  }
  
  // Decrement for characters in t
  for (const char of t) {
    const count = freq.get(char);
    if (!count || count === 0) return false;
    freq.set(char, count - 1);
  }
  
  return true;
}

Optimized version using array:

function isAnagramArray(s: string, t: string): boolean {
  if (s.length !== t.length) return false;
  
  const freq = new Array(26).fill(0);
  
  for (let i = 0; i < s.length; i++) {
    freq[s.charCodeAt(i) - 'a'.charCodeAt(0)]++;
    freq[t.charCodeAt(i) - 'a'.charCodeAt(0)]--;
  }
  
  return freq.every(count => count === 0);
}

Time: O(n), Space: O(1) for array, O(k) for Map where k is alphabet size

Pattern 2: Group Anagrams

Group strings that are anagrams of each other.

function groupAnagrams(strs: string[]): string[][] {
  const map = new Map<string, string[]>();
  
  for (const str of strs) {
    // Create canonical key: sorted characters
    const key = str.split('').sort().join('');
    
    if (!map.has(key)) {
      map.set(key, []);
    }
    map.get(key)!.push(str);
  }
  
  return Array.from(map.values());
}

Alternative using frequency count as key:

function groupAnagramsFreq(strs: string[]): string[][] {
  const map = new Map<string, string[]>();
  
  for (const str of strs) {
    const freq = new Array(26).fill(0);
    for (const char of str) {
      freq[char.charCodeAt(0) - 'a'.charCodeAt(0)]++;
    }
    const key = freq.join(',');
    
    if (!map.has(key)) {
      map.set(key, []);
    }
    map.get(key)!.push(str);
  }
  
  return Array.from(map.values());
}

Time: O(n k log k) for sort, O(n k) for frequency count

Space: O(n * k)

Pattern 3: First Non-Repeating Character

Find the first character that appears exactly once.

function firstUniqChar(s: string): number {
  const freq = new Map<string, number>();
  
  // Count frequencies
  for (const char of s) {
    freq.set(char, (freq.get(char) || 0) + 1);
  }
  
  // Find first character with count 1
  for (let i = 0; i < s.length; i++) {
    if (freq.get(s[i]) === 1) {
      return i;
    }
  }
  
  return -1;
}

Time: O(n), Space: O(k) where k is alphabet size

Pattern 4: Valid Anagram with Constraints

Check if two strings are anagrams, handling Unicode and case sensitivity.

function isAnagramUnicode(s: string, t: string): boolean {
  if (s.length !== t.length) return false;
  
  const freq = new Map<string, number>();
  
  // Normalize and count
  for (const char of s.toLowerCase()) {
    if (/[a-z0-9]/.test(char)) {
      freq.set(char, (freq.get(char) || 0) + 1);
    }
  }
  
  // Decrement
  for (const char of t.toLowerCase()) {
    if (/[a-z0-9]/.test(char)) {
      const count = freq.get(char);
      if (!count || count === 0) return false;
      freq.set(char, count - 1);
    }
  }
  
  return Array.from(freq.values()).every(count => count === 0);
}

Advanced Patterns

Pattern 5: Minimum Window Substring (with Frequency)

Find the smallest substring containing all characters of another string with correct frequencies.

function minWindow(s: string, t: string): string {
  const need = new Map<string, number>();
  for (const char of t) {
    need.set(char, (need.get(char) || 0) + 1);
  }
  
  const window = new Map<string, number>();
  let left = 0, right = 0;
  let valid = 0; // Count of satisfied requirements
  let start = 0, len = Infinity;
  
  while (right < s.length) {
    const c = s[right];
    right++;
    
    if (need.has(c)) {
      window.set(c, (window.get(c) || 0) + 1);
      if (window.get(c) === need.get(c)) {
        valid++;
      }
    }
    
    while (valid === need.size) {
      if (right - left < len) {
        start = left;
        len = right - left;
      }
      
      const d = s[left];
      left++;
      
      if (need.has(d)) {
        if (window.get(d) === need.get(d)) valid--;
        window.set(d, (window.get(d) || 0) - 1);
      }
    }
  }
  
  return len === Infinity ? "" : s.substring(start, start + len);
}

Pattern 6: Character Replacement

Find longest substring with at most K replacements of any character.

function characterReplacement(s: string, k: number): number {
  const freq = new Map<string, number>();
  let left = 0;
  let maxCount = 0; // Most frequent character count in current window
  let maxLen = 0;
  
  for (let right = 0; right < s.length; right++) {
    const char = s[right];
    freq.set(char, (freq.get(char) || 0) + 1);
    maxCount = Math.max(maxCount, freq.get(char)!);
    
    // Shrink if replacements needed exceed k
    while (right - left + 1 - maxCount > k) {
      freq.set(s[left], freq.get(s[left])! - 1);
      left++;
    }
    
    maxLen = Math.max(maxLen, right - left + 1);
  }
  
  return maxLen;
}

When to Use Character Frequency Maps

Use frequency counting when you see these signals:

• "Anagram" — Check if strings have same character counts
• "Frequency" or "Count" — Need to track how many times characters appear
• "Group anagrams" — Group strings with same character frequencies
• "First unique" or "Non-repeating" — Find characters with specific counts
• "Minimum window" — Need to match character frequencies in a substring
• "Character replacement" — Problems involving changing character frequencies

Template

function frequencyTemplate(s: string): number {
  const freq = new Map<string, number>();
  
  // Count frequencies
  for (const char of s) {
    freq.set(char, (freq.get(char) || 0) + 1);
  }
  
  // Process based on frequencies
  // ...
  
  return result;
}

Time and Space Complexity

• Time: O(n) for counting, O(n log n) if sorting is involved
• Space: O(k) where k is the size of the alphabet (O(1) for fixed alphabet like 26 letters)

Practice Tips

1. Choose the right structure — Array for fixed alphabet, Map for dynamic
2. Normalize early — Convert to lowercase if case-insensitive
3. Handle Unicode — Use Map for Unicode characters, not array
4. Optimize space — For lowercase-only, array is more efficient than Map
5. Watch for edge cases — Empty strings, single character, all same characters

Related Concepts

• Sliding Window — Often combined with frequency maps to track window state
• Two Pointers — Can use frequency maps to validate palindromes
• Hash Tables — Frequency maps are a special case of hash tables

Character frequency maps are a fundamental building block for many string algorithms. Master this pattern, and you'll find it appears in countless interview problems.