Longest Shared Route Segment

Hard

A country has cities cities numbered 0 to cities - 1, with a road between every pair. A few friends are travelling, and the route of each one is stored in routes[i] as the cities in the order visited. A city may appear in a route more than once, but never twice in a row. A **segment** of a route is a run of consecutive cities in it. Return the length (number of cities) of the longest segment that appears in every friend's route, or 0 if they share none.

Example 1

cities=6, routes=[[0, 1, 2, 3], [5, 1, 2, 3, 4], [2, 3, 1]] → 2

The leg 2 → 3 appears in all three routes. The longer 1 → 2 → 3 is missing from the third one.

Example 2

cities=4, routes=[[0, 1], [2, 3]] → 0

The routes share no city at all, so the answer is 0.

Example 3

cities=3, routes=[[0, 1, 0, 1], [1, 0, 1, 0]] → 3

Both routes contain 0 → 1 → 0 (and 1 → 0 → 1), but no run of four cities matches.

Constraints

1 ≤ cities ≤ 10⁵
2 ≤ len(routes) ≤ 10⁵
Every route is non-empty, and the routes have at most 10⁵ cities in total
0 ≤ routes[i][j] < cities
Neighbouring cities in a route are different

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Binary Search Suffix Array Hash Function Rolling Hash

Similar problems

Longest Repeated Fragment Hard Suffixes Echoing the Start Hard Phrase From Word Beginnings, Long Edition Hard Longest Shared Run Medium Longest Piece Seen Twice Medium

Input

cities=6, routes=[[0, 1, 2, 3], [5, 1, 2, 3, 4], [2, 3, 1]]

Expected

Run checks the first 3 tests in your browser. Submit checks all 58 tests on the server, hidden ones included.