0657MediumArrayBinary SearchDynamic ProgrammingSliding WindowRolling HashHash Function

Longest Shared Run of Road Segments

Tracked in this browser only

Trains the technique from

LeetCode 718Maximum Length of Repeated Subarray

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def longest_shared_run(route_a: list[int], route_b: list[int]) -> int:

Java

public int longestSharedRun(int[] routeA, int[] routeB)

The intended approach

Time O(n * m) where n and m are the two route lengths.Space O(m): two rows of the table.

Build the table whose entry for a pair of positions holds the length of the identical run that *ends* at those two legs. When the two legs carry the same segment id, that length is one more than the entry for the pair of positions just before them; when they differ, the run cannot end there at all and the entry is zero. Since each entry only reads the diagonal neighbour from the previous row, the code keeps the previous row and the row being filled and reports the largest entry ever written.

Pythonentry point: longest_shared_run

def longest_shared_run(route_a, route_b):
    # match[i][j] = length of the identical run that ends at leg i of route_a and
    # leg j of route_b. Only the previous row of that table is ever read, so two
    # rows are enough. O(n * m) time, O(m) space.
    m = len(route_b)
    prev = [0] * (m + 1)
    best = 0
    for i in range(len(route_a)):
        cur = [0] * (m + 1)
        ai = route_a[i]
        for j in range(m):
            if ai == route_b[j]:
                cur[j + 1] = prev[j] + 1
                if cur[j + 1] > best:
                    best = cur[j + 1]
        prev = cur
    return best

The obvious version

Take every pair of starting positions, one from each route, and walk both routes forward together for as long as the segment ids keep matching. Report the longest walk found.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_longest_shared_run(route_a, route_b):
    n = len(route_a)
    m = len(route_b)
    best = 0
    for i in range(n):
        for j in range(m):
            run = 0
            while i + run < n and j + run < m and route_a[i + run] == route_b[j + run]:
                run += 1
            if run > best:
                best = run
    return best

How this problem was checked

Reference solution executed against 11 test cases — 11 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in