FunctionRacerProblemsRace

Longest Shared Passage

EasyDynamic programmingPython, JavaScript, TypeScript, Java, C++

first and second are two melodies written as lists of note numbers. A passage is a run of consecutive notes.

Return the length of the longest passage that appears in both melodies, with the same notes in the same order. It may start at different positions in the two melodies. Return 0 if the melodies have no note in common, or if either one is empty.

Example 1

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

The passage 7, 2, 9 is in both melodies. 5, 7 is shared too, but it is shorter.

Example 2

first [4,4,4]
second [8,6]
returns 0

No note of the first melody occurs in the second.

Constraints

Race itor take your time

Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.

More Dynamic programming problems