Слова без повторов
Дан текст — последовательность слов. Найдите самый длинный кусок подряд идущих слов, в котором ни одно слово не встречается дважды. Если таких кусков несколько, выведите самый левый.
Второй тест — первый том «Войны и мира», третий — начало романа в переводе Луизы и Эйлмера Мод. Во всём романе самый длинный такой кусок — 68 слов; он в третьем томе и начинается словами «наглый голиаф от пределов франции».
Вход
В первой строке n (1 ≤ n ≤ 2·10⁵), во второй — n слов через пробел, из строчных букв, не длиннее 30 символов.
Выход
Два числа: длина самого длинного куска и номер его первого слова (слова нумеруются с единицы).
Примеры
Пример 1
7 do re re do mi fa sol
5 3
Ограничения
- Время · Python
- 4000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 8 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Если кусок от l до r без повторов, то и любой кусок внутри него без повторов. Значит, когда правый край сдвигается вправо, левому никогда не нужно возвращаться назад.
2Идея
Два указателя: правый идёт по словам одно за другим, левый — граница окна без повторов. Для каждого слова помним, где мы видели его в последний раз. Если новое слово уже было внутри окна, левый край перепрыгивает сразу за его прошлую копию: всё, что левее, теперь содержит повтор.
3Разбор
«Где видели в последний раз» хранит хеш-таблица слово → позиция. Важна проверка, что прошлая копия внутри окна: если она левее левого края, она уже не мешает, и двигать левый край назад нельзя.
Самый левый ответ получается сам: окно обновляет ответ, только если стало строго длиннее.
3+Решение
4Сложность
Правый указатель проходит слова один раз, левый только прыгает вперёд: O(n) операций с хеш-таблицей, в среднем O(n) времени.
5Типичные ошибки
- Левый край назад. Если не проверить, что прошлая копия внутри окна, левый край может прыгнуть влево, и окно «вспомнит» повторы, которые уже выбросило. Пример из условия ловит именно это.
- Перебор начал. Для каждого начала растить окно до первого повтора — O(n·L), а в четвёртом тесте повторов нет совсем.
- Не самый левый ответ. Обновлять ответ при равной длине — значит вывести последний из равных.