Вопрос нужен, чтобы оценить, понимает ли кандидат, как модифицировать алгоритм поиска анаграмм для возврата всех позиций.
Для поиска всех индексов используется тот же алгоритм со скользящим окном. При каждом совпадении частот текущего окна с эталоном сохраняется индекс начала окна. В результате возвращается массив всех позиций. Алгоритм остаётся линейным по времени.
Поиск индексов — это логическое расширение задачи поиска самих анаграмм.
Используется тот же sliding window, но дополнительно:
отслеживается текущая позиция окна
при совпадении частот сохраняется индекс
Подготовка
частотная карта подстроки
пустой массив результатов
Инициализация окна
первые k символов строки
Сдвиг окна
добавление нового символа
удаление старого
Проверка совпадения
если карты равны → push(startIndex)
const result = []
// при совпадении:
result.push(startIndex)
корректное обновление частот при сдвиге
одинаковый размер окна
аккуратная работа с символами, частота которых стала нулевой
использование массивов вместо объектов для ограниченного алфавита
счётчик совпавших символов вместо полного сравнения карт
Все индексы анаграмм находятся тем же алгоритмом скользящего окна, что и одиночные вхождения. Разница лишь в накоплении результатов, а асимптотика остаётся линейной.