Почему это работает
- Ответ — это n слов подряд, поэтому окно фиксированное, n · L букв, и сдвигается на целое слово: одно слово входит, одно уходит, seen обновляется за O(1).
- Сдвиг на слово проходит только начала offset, offset + L, …, поэтому проходы от 0 до L - 1 вместе пробуют каждое начало. Здесь «tobe» с индекса 1 видит только проход от 1.
- В окне ровно n слов, поэтому если у каждого слова счётчик как в need, места для чужих не остаётся: окно — это наши слова в каком-то порядке.
Сложность
Время O(|s| · (L + n)): L проходов вместе дают около |s| шагов, и на каждом шаге вырезается слово из L букв и проверяется need, где не больше n слов. Память O(n · L + |s|): need хранит слова, а seen — каждое слово, встреченное за проход, даже ушедшее, со счётчиком 0.
дальшеТеперь реши её сам, без подсказок.
Решить на LeetCode ↗