[AlgoMastery]
Topics›String›Character Counting
📖

Character Counting

String
~20 min read
5 practice problems

Overview

Character counting is a fundamental technique in string algorithms where you track how many times each character appears in a string. This simple concept forms the basis for solving many complex string problems efficiently. Character counting problems test your understanding of hash maps, arrays, sliding windows, and frequency analysis.

Character counting is used in:

  • Finding first/last unique characters
  • Validating character frequencies
  • Counting distinct characters
  • Character replacement problems
  • Frequency-based transformations
  • Pattern matching with frequency constraints

Data Structures for Character 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 time
  • Memory efficient for fixed alphabets
  • Faster than Map for small alphabets

Use when: Alphabet size is small and fixed (e.g., lowercase letters a-z)

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)
  • Dynamic size
  • No need to know alphabet size

Use when: Alphabet size is unknown or characters are arbitrary

Option 3: Object/Record (JavaScript)

function countFrequencyObject(s: string): Record<string, number> {
  const freq: Record<string, number> = {};
  for (const char of s) {
    freq[char] = (freq[char] || 0) + 1;
  }
  return freq;
}

Advantages:

  • Simple syntax
  • Good for small to medium strings

Use when: You prefer object syntax and don't need Map-specific features

Pattern 1: First Non-Repeating Character

Find the first character that appears exactly once.

Approach: Count frequencies, then find first character with count 1.

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;
}

Optimized with array:

function firstUniqCharArray(s: string): number {
  const freq = new Array(26).fill(0);
  
  // Count frequencies
  for (const char of s) {
    freq[char.charCodeAt(0) - 'a'.charCodeAt(0)]++;
  }
  
  // Find first character with count 1
  for (let i = 0; i < s.length; i++) {
    if (freq[s.charCodeAt(i) - 'a'.charCodeAt(0)] === 1) {
      return i;
    }
  }
  
  return -1;
}

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

Variation: Find first non-repeating character (return character, not index):

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

Pattern 2: Last Non-Repeating Character

Find the last character that appears exactly once.

function lastUniqChar(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 last character with count 1
  for (let i = s.length - 1; i >= 0; i--) {
    if (freq.get(s[i]) === 1) {
      return i;
    }
  }
  
  return -1;
}

Time: O(n), Space: O(k)

Pattern 3: Count Distinct Characters

Count how many unique characters appear in a string.

Approach 1: Using Set

function countDistinct(s: string): number {
  return new Set(s).size;
}

Approach 2: Using Frequency Map

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

Time: O(n), Space: O(k)

Variation: Count distinct characters in a substring (sliding window):

function countDistinctInWindow(s: string, k: number): number[] {
  const results: number[] = [];
  const freq = new Map<string, number>();
  
  // Initialize first window
  for (let i = 0; i < k; i++) {
    freq.set(s[i], (freq.get(s[i]) || 0) + 1);
  }
  results.push(freq.size);
  
  // Slide window
  for (let i = k; i < s.length; i++) {
    // Remove left character
    const leftChar = s[i - k];
    const count = freq.get(leftChar)!;
    if (count === 1) {
      freq.delete(leftChar);
    } else {
      freq.set(leftChar, count - 1);
    }
    
    // Add right character
    freq.set(s[i], (freq.get(s[i]) || 0) + 1);
    
    results.push(freq.size);
  }
  
  return results;
}

Pattern 4: Most Frequent Character

Find the character that appears most frequently.

function mostFrequentChar(s: string): string {
  const freq = new Map<string, number>();
  
  // Count frequencies
  for (const char of s) {
    freq.set(char, (freq.get(char) || 0) + 1);
  }
  
  // Find maximum
  let maxCount = 0;
  let maxChar = '';
  
  for (const [char, count] of freq) {
    if (count > maxCount) {
      maxCount = count;
      maxChar = char;
    }
  }
  
  return maxChar;
}

Return all characters with maximum frequency:

function mostFrequentChars(s: string): string[] {
  const freq = new Map<string, number>();
  
  for (const char of s) {
    freq.set(char, (freq.get(char) || 0) + 1);
  }
  
  const maxCount = Math.max(...Array.from(freq.values()));
  const result: string[] = [];
  
  for (const [char, count] of freq) {
    if (count === maxCount) {
      result.push(char);
    }
  }
  
  return result;
}

Time: O(n), Space: O(k)

Pattern 5: Characters with Specific Frequency

Find all characters that appear exactly K times.

function charsWithFrequency(s: string, k: number): string[] {
  const freq = new Map<string, number>();
  
  for (const char of s) {
    freq.set(char, (freq.get(char) || 0) + 1);
  }
  
  const result: string[] = [];
  for (const [char, count] of freq) {
    if (count === k) {
      result.push(char);
    }
  }
  
  return result;
}

Find characters appearing at least K times:

function charsWithMinFrequency(s: string, k: number): string[] {
  const freq = new Map<string, number>();
  
  for (const char of s) {
    freq.set(char, (freq.get(char) || 0) + 1);
  }
  
  const result: string[] = [];
  for (const [char, count] of freq) {
    if (count >= k) {
      result.push(char);
    }
  }
  
  return result;
}

Find characters appearing at most K times:

function charsWithMaxFrequency(s: string, k: number): string[] {
  const freq = new Map<string, number>();
  
  for (const char of s) {
    freq.set(char, (freq.get(char) || 0) + 1);
  }
  
  const result: string[] = [];
  for (const [char, count] of freq) {
    if (count <= k) {
      result.push(char);
    }
  }
  
  return result;
}

Pattern 6: Character Frequency Distribution

Get a sorted list of characters by frequency (most frequent first).

function charsByFrequency(s: string): Array<[string, number]> {
  const freq = new Map<string, number>();
  
  for (const char of s) {
    freq.set(char, (freq.get(char) || 0) + 1);
  }
  
  return Array.from(freq.entries()).sort((a, b) => b[1] - a[1]);
}

Sort by character if frequencies are equal:

function charsByFrequencySorted(s: string): Array<[string, number]> {
  const freq = new Map<string, number>();
  
  for (const char of s) {
    freq.set(char, (freq.get(char) || 0) + 1);
  }
  
  return Array.from(freq.entries()).sort((a, b) => {
    if (b[1] !== a[1]) {
      return b[1] - a[1]; // Sort by frequency descending
    }
    return a[0].localeCompare(b[0]); // Then by character ascending
  });
}

Time: O(n + k log k) where k is distinct characters

Pattern 7: Reorganize String by Frequency

Rearrange string so no two same characters are adjacent, prioritizing most frequent.

function reorganizeString(s: string): string {
  const freq = new Map<string, number>();
  for (const char of s) {
    freq.set(char, (freq.get(char) || 0) + 1);
  }
  
  // Check if reorganization is possible
  const maxCount = Math.max(...Array.from(freq.values()));
  if (maxCount > Math.ceil(s.length / 2)) {
    return ''; // Impossible
  }
  
  // Sort by frequency
  const sorted = Array.from(freq.entries()).sort((a, b) => b[1] - a[1]);
  
  const result: string[] = new Array(s.length);
  let index = 0;
  
  // Fill even positions first, then odd
  for (const [char, count] of sorted) {
    for (let i = 0; i < count; i++) {
      if (index >= s.length) index = 1; // Switch to odd positions
      result[index] = char;
      index += 2;
    }
  }
  
  return result.join('');
}

Time: O(n + k log k), Space: O(n)

Pattern 8: Character Replacement Based on Frequency

Replace characters to maximize frequency of a target character.

function maxFrequencyAfterReplacement(s: string, k: number, targetChar: string): number {
  const freq = new Map<string, number>();
  let left = 0;
  let maxCount = 0; // Count of targetChar 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);
    
    if (char === targetChar) {
      maxCount = Math.max(maxCount, freq.get(char)!);
    }
    
    // Shrink if replacements needed exceed k
    // Window size - maxCount = characters to replace
    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;
}

Time: O(n), Space: O(k)

Pattern 9: Validate Character Frequency Constraints

Check if string satisfies frequency constraints.

All characters appear at least K times:

function allCharsAtLeastK(s: string, k: number): boolean {
  const freq = new Map<string, number>();
  
  for (const char of s) {
    freq.set(char, (freq.get(char) || 0) + 1);
  }
  
  for (const count of freq.values()) {
    if (count < k) {
      return false;
    }
  }
  
  return true;
}

At most one character appears odd times (palindrome check):

function canFormPalindrome(s: string): boolean {
  const freq = new Map<string, number>();
  
  for (const char of s) {
    freq.set(char, (freq.get(char) || 0) + 1);
  }
  
  let oddCount = 0;
  for (const count of freq.values()) {
    if (count % 2 === 1) {
      oddCount++;
    }
  }
  
  return oddCount <= 1;
}

All characters appear even times:

function allCharsEven(s: string): boolean {
  const freq = new Map<string, number>();
  
  for (const char of s) {
    freq.set(char, (freq.get(char) || 0) + 1);
  }
  
  for (const count of freq.values()) {
    if (count % 2 !== 0) {
      return false;
    }
  }
  
  return true;
}

Pattern 10: Character Frequency in Sliding Window

Track character frequencies in a sliding window.

function slidingWindowFrequencies(s: string, k: number): Map<string, number>[] {
  const results: Map<string, number>[] = [];
  const freq = new Map<string, number>();
  
  // Initialize first window
  for (let i = 0; i < k; i++) {
    freq.set(s[i], (freq.get(s[i]) || 0) + 1);
  }
  results.push(new Map(freq));
  
  // Slide window
  for (let i = k; i < s.length; i++) {
    // Remove left
    const leftChar = s[i - k];
    const leftCount = freq.get(leftChar)!;
    if (leftCount === 1) {
      freq.delete(leftChar);
    } else {
      freq.set(leftChar, leftCount - 1);
    }
    
    // Add right
    freq.set(s[i], (freq.get(s[i]) || 0) + 1);
    
    results.push(new Map(freq));
  }
  
  return results;
}

Time: O(n k), Space: O(n k)

Pattern 11: Character Frequency Comparison

Compare character frequencies between two strings.

function compareFrequencies(s1: string, s2: string): boolean {
  const freq1 = new Map<string, number>();
  const freq2 = new Map<string, number>();
  
  for (const char of s1) {
    freq1.set(char, (freq1.get(char) || 0) + 1);
  }
  
  for (const char of s2) {
    freq2.set(char, (freq2.get(char) || 0) + 1);
  }
  
  if (freq1.size !== freq2.size) return false;
  
  for (const [char, count] of freq1) {
    if (freq2.get(char) !== count) {
      return false;
    }
  }
  
  return true;
}

Find frequency difference:

function frequencyDifference(s1: string, s2: string): Map<string, number> {
  const diff = new Map<string, number>();
  
  // Count s1
  for (const char of s1) {
    diff.set(char, (diff.get(char) || 0) + 1);
  }
  
  // Subtract s2
  for (const char of s2) {
    diff.set(char, (diff.get(char) || 0) - 1);
  }
  
  // Remove zeros
  for (const [char, count] of diff) {
    if (count === 0) {
      diff.delete(char);
    }
  }
  
  return diff;
}

Pattern 12: Character Frequency Statistics

Get comprehensive statistics about character frequencies.

interface FrequencyStats {
  total: number;
  distinct: number;
  mostFrequent: string;
  leastFrequent: string;
  averageFrequency: number;
  medianFrequency: number;
}

function getFrequencyStats(s: string): FrequencyStats {
  const freq = new Map<string, number>();
  
  for (const char of s) {
    freq.set(char, (freq.get(char) || 0) + 1);
  }
  
  const frequencies = Array.from(freq.values()).sort((a, b) => a - b);
  const total = s.length;
  const distinct = freq.size;
  
  let mostFrequent = '';
  let maxCount = 0;
  let leastFrequent = '';
  let minCount = Infinity;
  
  for (const [char, count] of freq) {
    if (count > maxCount) {
      maxCount = count;
      mostFrequent = char;
    }
    if (count < minCount) {
      minCount = count;
      leastFrequent = char;
    }
  }
  
  const averageFrequency = total / distinct;
  const medianFrequency = frequencies.length % 2 === 0
    ? (frequencies[frequencies.length / 2 - 1] + frequencies[frequencies.length / 2]) / 2
    : frequencies[Math.floor(frequencies.length / 2)];
  
  return {
    total,
    distinct,
    mostFrequent,
    leastFrequent,
    averageFrequency,
    medianFrequency
  };
}

When to Use Character Counting

Use character counting when:

  • Problem asks about "frequency", "count", or "occurrence"
  • Need to find "first unique" or "non-repeating" characters
  • Validating character frequency constraints
  • Comparing character distributions
  • Sliding window problems requiring frequency tracking
  • Anagram or permutation problems

Template (Basic Counting)

function countTemplate(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;
}

Template (Array for Fixed Alphabet)

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

Template (Sliding Window with Frequency)

function slidingWindowCountTemplate(s: string, k: number): void {
  const freq = new Map<string, number>();
  
  // Initialize window
  for (let i = 0; i < k; i++) {
    freq.set(s[i], (freq.get(s[i]) || 0) + 1);
  }
  
  // Process first window
  // ...
  
  // Slide window
  for (let i = k; i < s.length; i++) {
    // Remove left
    const leftCount = freq.get(s[i - k])!;
    if (leftCount === 1) freq.delete(s[i - k]);
    else freq.set(s[i - k], leftCount - 1);
    
    // Add right
    freq.set(s[i], (freq.get(s[i]) || 0) + 1);
    
    // Process window
    // ...
  }
}

Time and Space Complexity Summary

  • Basic counting: O(n) time, O(k) space where k is alphabet size
  • Array counting: O(n) time, O(1) space for fixed alphabet
  • Sliding window: O(n) time, O(k) space
  • Sorting frequencies: O(n + k log k) time, O(k) space

Practice Tips

  1. Choose the right structure — Array for fixed alphabet (a-z), Map for dynamic
  2. Optimize space — Use array when alphabet size is small and known
  3. Handle edge cases — Empty strings, single character, all same characters
  4. Combine with sliding window — For substring frequency problems
  5. Use frequency for validation — Check constraints efficiently
  6. Consider Unicode — Use Map for Unicode characters

Common Mistakes

  1. Forgetting to initialize — Always initialize frequency structures
  2. Off-by-one errors — Be careful with array indices
  3. Not handling empty strings — Check length before processing
  4. Case sensitivity — Normalize if case-insensitive comparison needed
  5. Unicode handling — Use Map for multi-byte characters

Related Concepts

  • Character Frequency Maps — Core technique for counting
  • Sliding Window — Often combined with frequency counting
  • Hash Maps — Essential data structure for counting
  • Anagram Problems — Rely heavily on character counting
  • String Validation — Uses frequency constraints

Character counting is a fundamental building block for many string algorithms. Master these patterns, and you'll be able to solve a wide variety of frequency-based problems efficiently. Practice with different data structures and understand when to use each approach.

← PreviousAnagram ProblemsNext →String Compression