438. Find All Anagrams in a String

Задача

Даны две строки s и p . Верните массив всех начальных индексов анаграмм строки p в строке s . Вы можете вернуть ответ в любом порядке.

Примеры

Пример 1

Input: s = "cbaebabacd", p = "abc"
Output: [0,6]

Пояснение

Подстрока с индекса 0 — “cba”, с индекса 6 — “bac”; обе анаграммы “abc”.

Пример 2

Input: s = "abab", p = "ab"
Output: [0,1,2]

Пояснение

Подстроки с индексов 0 (“ab”), 1 (“ba”) и 2 (“ab”) — все анаграммы “ab”.

Решение

Решение

/**
 * Time Complexity: O(N) — где N длина строки s.
 * Space Complexity: O(1) — так как размер словаря/массива фиксирован (26 букв).
 */
var findAnagrams = function(s, p) {
    const result = [];
    if (s.length < p.length) return result;
 
    const pCount = new Array(26).fill(0);
    const sCount = new Array(26).fill(0);
    const aCode = 'a'.charCodeAt(0);
 
    // 1. Инициализируем статистику для первой части окна
    for (let i = 0; i < p.length; i++) {
        pCount[p.charCodeAt(i) - aCode]++;
        sCount[s.charCodeAt(i) - aCode]++;
    }
 
    // Проверяем самое первое окно (индекс 0)
    if (arraysEqual(pCount, sCount)) {
        result.push(0);
    }
 
    // 2. Скользящее окно: начинаем двигаться с p.length до конца s
    let left = 0;
    for (let right = p.length; right < s.length; right++) {
        // Добавляем новую букву справа
        sCount[s.charCodeAt(right) - aCode]++;
 
        // Убираем старую букву слева
        sCount[s.charCodeAt(left) - aCode]--;
        left++;
 
        // Сравниваем массивы частот
        if (arraysEqual(pCount, sCount)) {
            result.push(left);
        }
    }
 
    return result;
};
 
// Вспомогательная функция для сравнения массивов частот
function arraysEqual(arr1, arr2) {
    for (let i = 0; i < 26; i++) {
        if (arr1[i] !== arr2[i]) return false;
    }
    return true;
}

Решение 2

/**
 * Time Complexity: O(N) 
 * - Мы проходим по строке s ровно один раз с помощью двух указателей left и right.
 * - Все операции внутри цикла (доступ к объекту, инкремент) занимают O(1).
 * 
 * Space Complexity: O(1)
 * - Храним map для букв (максимум 26 ключей, либо чуть больше, но константный размер алфавита).
 * 
 * Логика работы (Sliding Window):
 * 1. neededChars хранит частоту букв, которые нам НУЖНО найти (положительные числа).
 * 2. Расширяем окно вправо (right++):
 *    - Если буква нужна (neededChars[char] > 0), уменьшаем count (осталось найти меньше).
 *    - В любом случае уменьшаем счетчик в map. Если он станет отрицательным, значит в окне "избыток" этой буквы.
 * 3. Если count === 0, значит все нужные буквы сейчас в окне в правильном количестве -> нашли анаграмму.
 * 4. Сужаем окно слева (left++), если оно достигло размера p.length:
 *    - Возвращаем букву s[left] обратно в статистику.
 *    - Если её счетчик стал >= 0 (то есть она была нужна и мы её "потеряли"), увеличиваем count.
 */
var findAnagrams = function(s, p) {
    const res = [];
    const neededChars = {};
 
    // Инициализация частотной карты для паттерна p
    for (let char of p) {
        neededChars[char] = (neededChars[char] || 0) + 1;
    }
 
    let left = 0;
    let right = 0;
    let count = p.length; // Сколько полезных символов осталось найти
 
    while (right < s.length) {
        // --- РАСШИРЕНИЕ ОКНА (RIGHT) ---
        // Если текущая буква есть в p и она еще "нужна" (счетчик > 0)
        if (neededChars[s[right]] > 0) {
            count--;
        }
 
        // Уменьшаем счетчик (может уйти в минус, если буква лишняя или её нет в p)
        neededChars[s[right]] = (neededChars[s[right]] || 0) - 1;
        right++;
 
        // --- ПРОВЕРКА ---
        // Если count 0, значит нашли все буквы
        if (count === 0) res.push(left);
 
        // --- СУЖЕНИЕ ОКНА (LEFT) ---
        // Окно стало размером с p, пора двигать левую границу
        if (right - left === p.length) {
            // Если уходящая буква была "полезной" (счетчик >= 0),
            // значит мы теряем нужную букву, увеличиваем долг (count++)
            if (neededChars[s[left]] >= 0) {
                count++;
            }
 
            // Восстанавливаем счетчик буквы
            neededChars[s[left]]++;
            left++;
        }
    }
 
    return res;
};