Техпрогон
ВойтиНачать бесплатно
Выбор ответа Middle Скользящее окно обновлено

Поиск анаграммы в строке

Вопрос

Найти все позиции в s, где начинается анаграмма строки p. Какой размер окна и что в нём хранить?

Попробуйте сами

Выберите вариант, и откроется разбор.

Показать ответ и разбор

Коротко

Правильный ответ: Окно длины p.length, хранить счётчики букв. Анаграмма имеет ровно длину p, поэтому окно фиксированное.

Варианты ответа

  1. Окно переменной длины, в нём хранить Set букв
  2. Окно длины 1, сравнивать символы s и p по одному
  3. Окно длины s.length / 2, хранить отсортированную строку
  4. Окно длины p.length, хранить счётчики буквправильный ответ

Разбор

Анаграмма имеет ровно длину p, поэтому окно фиксированное. Храним частоты букв окна и сравниваем с частотами p (через счётчик совпадений за O(1) или массив из 26 за O(26)). Итого O(n).

  • Set не учитывает количество повторов.
  • Окно длины 1 не видит перестановок.
  • Длина окна задана p, а не s.

Ответьте сами, а не прочитайте

В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.

Потренироваться бесплатно

Предыдущий вопрос

Сумма максимумов всех окон длины k

Следующий вопрос

Объясни скользящее окно

Урок по теме

Паттерн: Скользящее окно

Термины по теме

Скользящее окно

Ещё по теме «Скользящее окно»

Все вопросы модуля