Вопрос нужен, чтобы оценить, понимает ли кандидат алгоритмический подход к поиску анаграмм, а не перебор всех вариантов.
Поиск анаграмм реализуется с помощью скользящего окна и частотных таблиц символов. Сначала считается частота символов искомой подстроки, затем окно той же длины «скользит» по строке. При совпадении частот найдено вхождение. Такой алгоритм работает за линейное время.
Задача поиска анаграмм — классический пример применения техники sliding window.
Анаграмма — это:
те же символы
в любом порядке
с тем же количеством повторений
Порядок символов не важен, важна частота.
Наивное решение:
брать каждую подстроку
сортировать символы
сравнивать с отсортированным образцом
Минусы:
сортировка на каждом шаге
сложность выше линейной
Идея:
Построить частотную карту подстроки pattern
Вести частотную карту текущего окна в строке
Сдвигать окно на один символ
Обновлять частоты, не пересчитывая всё заново
// частоты pattern и текущего окна сравниваются
// если совпали — найдено вхождение
Важно:
длина окна всегда равна длине подстроки
добавляем символ справа
убираем символ слева
каждый символ добавляется и удаляется один раз
нет вложенных циклов
сложность O(n)
Поиск анаграмм подстроки в строке эффективно решается через скользящее окно и частотные карты. Это позволяет избежать перебора и сортировки.