Задача 438 «Найти все анаграммы в строке» — это распространенная задача кодирования, которую можно решить с помощью метода скользящего окна и подсчета частот. Цель — найти все начальные индексы анаграмм более короткой строки (шаблона) внутри более длинной строки.

Вот пошаговое объяснение проблемы:

Постановка задачи: по двум строкам: s (более длинная строка) и p (более короткая строка) найти все начальные индексы анаграмм p в s.

Анаграмма — это слово или фраза, образованная путем перестановки букв другого слова, обычно с использованием всех исходных букв ровно один раз.

Пример:

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

Пояснение: В данном примере «abc» — это более короткая строка (шаблон), которая образует анаграмму «cbaebabacd», начиная с индексов 0 и 6.

Подход: Чтобы эффективно решить эту проблему, вы можете использовать метод скользящего окна вместе с подсчетом частоты символов. Вот как работает этот подход:

  1. Создайте два массива, pCount и sCount, оба размером 26, чтобы представить частоту каждого символа (от «a» до «z») в строке шаблона p и скользящем окне в строке s соответственно. Инициализируйте оба массива нулями.
  2. Сначала заполните массив pCount частотами символов в строке p с помощью цикла.
  3. Инициализируйте скользящее окно в s того же размера, что и шаблон p. Заполните массив sCount частотами символов в этом окне.
  4. Продвигайте окно по строке s слева направо, обновляя массив sCount по мере продвижения. На каждом шаге проверяйте, соответствует ли массив sCount массиву pCount. Если они совпадают, это означает, что найдена анаграмма p, и вы записываете в результат начальный индекс анаграммы.
  5. После каждого шага удаляйте самый левый символ из скользящего окна и добавляйте новый символ справа.
  6. Продолжайте этот процесс, пока скользящее окно не пройдет через всю строку s.
  7. Наконец, верните список начальных индексов, в которых анаграммы p были найдены в s.
/**
 * @param {string} s
 * @param {string} p
 * @return {number[]}
 */
var findAnagrams = function(s, p) {
    if (s.length < p.length) {
        return []; // If s is shorter than p, there can be no anagrams, so return an empty array.
    }

    const pCount = new Array(26).fill(0); // Array to store character frequency of string p (26 characters from 'a' to 'z').
    const sCount = new Array(26).fill(0); // Array to store character frequency in the sliding window.
    const result = [];

    // Calculate character frequency of string p.
    for (let i = 0; i < p.length; i++) {
        // Get the Unicode code point of character p[i]. For example, if p[0] = 'a', the code point is 97.
        // Let's say. Calculate how far the current character is from 'a' by subtracting the code point of 'a'.
        // codePoint - 'a'.charCodeAt(0) = 97 - 97 = 0
        // Thus, the current character 'a' is stored at index 0 in the array.
        pCount[p.charCodeAt(i) - 'a'.charCodeAt(0)]++;
    }

    // Initialize the sliding window.
    for (let i = 0; i < p.length; i++) {
        sCount[s.charCodeAt(i) - 'a'.charCodeAt(0)]++;
    }

    // Iterate through string s using a sliding window.
    for (let i = p.length; i < s.length; i++) {
        // Check if the character frequency in the current sliding window matches p.
        if (isEqual(pCount, sCount)) {
            result.push(i - p.length);
        }

        // Update the sliding window by removing the leftmost character and adding the new character.
        sCount[s.charCodeAt(i) - 'a'.charCodeAt(0)]++;
        sCount[s.charCodeAt(i - p.length) - 'a'.charCodeAt(0)]--;
    }

    // Check one more time after the loop ends.
    if (isEqual(pCount, sCount)) {
        result.push(s.length - p.length);
    }

    return result;
};

// Function to check if two character frequency arrays are equal.
function isEqual(arr1, arr2) {
    for (let i = 0; i < 26; i++) {
        if (arr1[i] !== arr2[i]) {
            return false;
        }
    }
    return true;
}

console.log(findAnagrams("cbaebabacd", "abc")); // Output: [0, 6]

Анализ сложности:

  • Временная сложность: O(N), где N — длина строки s. Это связано с тем, что мы проходим всю строку один раз с помощью скользящего окна.
  • Пространственная сложность: O(1), так как размер массивов pCount и sCount постоянен (26), а остальное использование пространства минимально.

Этот подход эффективно находит все начальные индексы анаграмм шаблона p внутри строки s без необходимости использования вложенных циклов или лишнего пространства.

Похожие проблемы:

3. Самая длинная подстрока без повторяющихся символов

76. Минимальная подстрока окна

239. Максимум скользящего окна

424. Замена самого длинного повторяющегося символа

567. Перестановка в строке