Longest Shared Run

Medium

You get two integer arrays, first and second. Find the longest contiguous run of elements that appears in both arrays, and return its length. If the arrays share no elements, return 0.

Example 1

first=[7, 2, 5, 5, 9, 1], second=[3, 2, 5, 5, 4] → 3

The run [2, 5, 5] appears contiguously in both arrays, so the length is 3.

Example 2

first=[1, 2, 3], second=[3, 2, 1] → 1

The arrays share elements, but only one matches in a row, so the answer is 1.

Example 3

first=[6, 6], second=[0, 8, 4] → 0

Constraints

1 ≤ len(first), len(second) ≤ 1000
0 ≤ first[i], second[i] ≤ 100

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Binary Search Dynamic Programming Sliding Window Hash Function Rolling Hash

Similar problems

Target From Word Beginnings Medium Phrase From Word Beginnings, Long Edition Hard Longest Piece Seen Twice Medium Two Separate Segments With a Given Sum Medium Trim and Extend a Word Medium

Input

first=[7, 2, 5, 5, 9, 1], second=[3, 2, 5, 5, 4]

Expected

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