Show problems as
Classic problem #718MediumArrayBinary SearchDynamic ProgrammingSliding WindowRolling HashHash Function

Maximum Length of Repeated Subarray

Real-world version: Longest Shared Run of Road Segments
Tracked in this browser only
Read Maximum Length of Repeated Subarray on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

Two delivery vans spent the day on the road, and each one's tracker wrote down the id of every road segment it drove, in order. route_a is the first van's list of legs and route_b is the second van's.

A dispatcher wants the longest piece of road the two vans covered identically: a run of consecutive legs taken from route_a that appears, in the same order and with no gaps, as a run of consecutive legs of route_b.

Return how many legs that longest run holds, or 0 when the vans never drove even a single segment in common.

Examples

Example 1

Input
route_a = [3, 6, 9, 12, 15, 18], route_b = [9, 12, 15, 18, 21]
Output
4

Legs 9, 12, 15, 18 sit consecutively in both lists, which is a shared run of four. Segment 21 is not in the first list and segments 3, 6 are not in the second, so the run cannot be stretched at either end.

Example 2

Input
route_a = [8, 4], route_b = [4, 4, 4]
Output
1

The only segment on both lists is 4, and the first van drove it once, so the shared run holds a single leg.

Example 3

Input
route_a = [11, 12, 13], route_b = [21, 22]
Output
0

No segment id appears on both lists, so the answer is 0.

Constraints

  • 1 <= route_a.length, route_b.length <= 1000
  • 0 <= route_a[i], route_b[i] <= 100

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def longest_shared_run(route_a: list[int], route_b: list[int]) -> int:
Java
public int longestSharedRun(int[] routeA, int[] routeB)

More on the same topics