#1923

Longest Common Subpath

international master · 1995 · lc hard +32 · premium · verified · 29.4% accepted · 512 likes · top 7%

Description

There is a country with n cities (0 to n - 1) and m friends, each traveling a path (a sequence of city indices with no two consecutive equal cities). Given n and array paths, return the length of the longest contiguous subpath common to all friends' paths, or 0 if none exists.

Example 1:

Input: n = 5, paths = [[0,1,2,3,4],

[2,3,4],

[4,0,1,2,3]]

Output: 2

Explanation: The longest common subpath is [2,3].

Example 2:

Input: n = 3, paths = [[0],[1],[2]]

Output: 0

Explanation: There is no common subpath shared by the three paths.

Example 3:

Input: n = 5, paths = [[0,1,2,3,4],

[4,3,2,1,0]]

Output: 1

Explanation: The possible longest common subpaths are [0], [1], [2], [3], and [4]. All have a length of 1.

Code

1

2

3

class Solution:
    def longestCommonSubpath(self, n: int, paths: List[List[int]]) -> int:

class Solution:
    def longestCommonSubpath(self, n: int, paths: List[List[int]]) -> int: