Задача: 438. Find All Anagrams in a String
Сложность: medium

Даны две строки s и p, вернуть массив всех начальных индексов анаграмм строки p в строке s. Ответ можно вернуть в любом порядке.
Анаграмма - это слово или фраза, образованные перестановкой букв другого слова или фразы, обычно с использованием всех исходных букв ровно один раз.

Пример:

Input: s = "cbaebabacd", p = "abc"
Output: [0,6]
Explanation:
The substring with start index = 0 is "cba", which is an anagram of "abc".
The substring with start index = 6 is "bac", which is an anagram of "abc".

👨‍💻 Алгоритм:

1⃣Построить эталонный счетчик pCount для строки p.

2⃣Передвигать скользящее окно по строке s: Пересчитывать счетчик скользящего окна sCount на каждом шаге, добавляя одну букву справа и удаляя одну букву слева.

3⃣Если sCount == pCount, обновить выходной список. Вернуть выходной список.

😎 Решение:

function findAnagrams($s, $p) {
    $ns = strlen($s);
    $np = strlen($p);
    if ($ns < $np) {
        return [];
    }

    $pCount = array_fill_keys(range('a', 'z'), 0);
    $sCount = array_fill_keys(range('a', 'z'), 0);

    for ($i = 0; $i < $np; $i++) {
        $pCount[$p[$i]]++;
    }

    $output = [];

    for ($i = 0; $i < $ns; $i++) {
        $sCount[$s[$i]]++;

        if ($i >= $np) {
            $leftChar = $s[$i - $np];
            if ($sCount[$leftChar] == 1) {
                unset($sCount[$leftChar]);
            } else {
                $sCount[$leftChar]--;
            }
        }

        if ($pCount == $sCount) {
            $output[] = $i - $np + 1;
        }
    }

    return $output;
}

Ставь 👍 и забирай 📚 Базу знаний