Words without repeats
A text is given as a sequence of words. Find the longest run of consecutive words in which no word occurs twice. If there are several such runs, output the leftmost.
The second test is the first volume of War and Peace (the Russian original), the third the beginning of the novel in the translation by Louise and Aylmer Maude. In the whole Russian novel the longest such run is 68 words; it is in the third volume and begins with the words «наглый голиаф от пределов франции» (“the insolent Goliath from the borders of France”).
Input
The first line holds n (1 ≤ n ≤ 2·10⁵), the second n words separated by spaces, made of lowercase letters, at most 30 characters long.
Output
Two numbers: the length of the longest run and the number of its first word (words are numbered from one).
Examples
Example 1
7 do re re do mi fa sol
5 3
Limits
- Time · Python
- 4000 ms
- Time · Go
- 1000 ms
- Memory
- 256 MB
- Judging
- 8 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
If the run from l to r has no repeats, then neither does any run inside it. So when the right edge moves right, the left one never needs to go back.
2The idea
Two pointers: the right one goes through the words one after another, the left one is the boundary of the window without repeats. For each word remember where we last saw it. If the new word was already inside the window, the left edge jumps straight past its previous copy: everything further left now contains a repeat.
3Walkthrough
“Where we last saw it” is kept by a hash table word → position. It is important to check that the previous copy is inside the window: if it is left of the left edge, it no longer gets in the way, and the left edge must not move backwards.
The leftmost answer comes by itself: the window updates the answer only if it has become strictly longer.
3+Solution
4Complexity
The right pointer passes over the words once, the left one only jumps forwards: O(n) hash table operations, O(n) time on average.
5Common mistakes
- The left edge going back. If you do not check that the previous copy is inside the window, the left edge may jump left, and the window “remembers” repeats it has already thrown out. The example in the statement catches exactly this.
- Enumerating starts. Growing a window from each start up to the first repeat is O(n·L), and the fourth test has no repeats at all.
- Not the leftmost answer. Updating the answer at equal length means outputting the last of the equal ones.