Подсчёт частоты

Проблема, которую мы решаем:

Тебя просят: подсчитай, сколько раз встречается каждая буква в “hello”. Один способ:

function countNaive(str) {
  // Для каждой буквы отсканируй строку и подсчитай
  for (let i = 0; i < str.length; i++) {
    let count = 0;
    for (let j = 0; j < str.length; j++) {
      if (str[i] === str[j]) count++;
    }
    console.log(str[i] + ": " + count);  // h: 1, e: 1, l: 2, l: 2, o: 1
  }
}

Это O(n²): для каждой из n букв ты сканируешь всю строку. Для больших входов это расточительно.

Идея подсчёта частоты:

Вместо этого отсканируй строку один раз. Для каждой буквы, которую ты встречаешь, обновляй её подсчёт в хеш-карте:

function countFreq(str) {
  const freq = new Map();  // карта частоты: буква → подсчёт
  
  for (let char of str) {
    // Инкрементируй подсчёт для этого символа
    freq.set(char, (freq.get(char) ?? 0) + 1);
  }
  
  // freq теперь содержит: h→1, e→1, l→2, o→1
  return freq;
}

Один цикл, O(n) времени. Одна хеш-карта, O(k) памяти, где k — количество уникальных букв.

Почему это работает:

• Первый проход: посети каждый элемент один раз. Добавь в карту если новый, инкрементируй если видел раньше.
• O(1) обновления: freq.set() и freq.get() это O(1) в среднем.
• Результат: после одного прохода, карта полная.

Хеш-карта против массива для маленьких алфавитов:

Если ключи это маленький фиксированный диапазон (например, строчные буквы a–z), ты можешь использовать обычный массив вместо хеш-карты:

function countFreqArray(str) {
  const freq = new Array(26).fill(0);  // 26 ячеек для a-z
  
  for (let char of str) {
    const index = char.charCodeAt(0) - 'a'.charCodeAt(0);  // 'a'→0, 'b'→1, и т.д.
    freq[index]++;
  }
  
  // freq[0] это подсчёт 'a', freq[1] это подсчёт 'b', и т.д.
  return freq;
}

Доступ к массиву это O(1) и немного быстрее чем операции хеш-карты (нет издержек хеширования). Оба работают; массив оптимизирован когда ключи маленькие и предсказуемые.

Общие применения карт частоты:

1. Анаграммы: две строки это анаграммы если они имеют одинаковые частоты символов.
2. Дубликаты и неповторяющиеся: найди элементы, что встречаются ровно один раз или больше чем один.
3. Самый/наименее частый: отслеживай элемент с самым высоким или низким подсчётом.
4. Группировка по частоте: организуй элементы по частоте.