#1923

Hard

auto_awesomeBinary search over the valid answer space

LeetCode Problem Workspace

Longest Common Subpath

The Longest Common Subpath problem requires finding the longest subpath shared by all paths in a graph using binary search and rolling hashes.

array binary search rolling hash suffix array hash function

Problem Statement

You are given a country with n cities connected by roads. Each city is numbered from 0 to n - 1. m friends are traveling through this country, and each one follows a path consisting of a sequence of cities. The paths are represented as a 2D integer array, where paths[i] is the path taken by the ith friend, consisting of a series of cities visited in order. Some cities may be visited more than once, but no city appears consecutively in the path.

Your task is to find the length of the longest common subpath shared by all friends' paths, or return 0 if there is no common subpath. A subpath is defined as a contiguous subsequence of cities, and it must appear in the same order in every friend's path.

Examples

Example 1

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

Output: 2

The longest common subpath is [2,3].

Example 2

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

Output: 0

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

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

Constraints

1 <= n <= 105
m == paths.length
2 <= m <= 105
sum(paths[i].length) <= 105
0 <= paths[i][j] < n
The same city is not listed multiple times consecutively in paths[i].

Solution Approach

Binary Search for Subpath Lengths

Start by performing a binary search over the length of the subpaths. The range of possible subpath lengths is from 0 to the length of the shortest path. This binary search efficiently narrows down the length of the longest common subpath by progressively verifying smaller or larger lengths.

Rolling Hash for Subpath Verification

For each candidate subpath length determined by the binary search, use a rolling hash to check whether there exists a common subpath of that length. The rolling hash technique allows for efficient comparison of subpaths by hashing them and checking for matching hash values across all paths.

Optimizing with Set Intersection

To confirm the existence of a common subpath, use set intersections of hashed values from different paths. If any subpath's hash is shared by all paths, then that subpath is a common subpath. The binary search narrows the search space, while the set intersection confirms the validity of the subpath.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity is driven by the binary search, which takes log(min_length) time, where min_length is the length of the shortest path. For each length tested, the rolling hash requires O(n) time for each path to compute and compare hashes, resulting in an overall time complexity of O(m * n * log(min_length)), where m is the number of paths and n is the average path length. The space complexity is O(m * n) due to the storage required for the rolling hash values of each path.

What Interviewers Usually Probe

Ability to implement efficient hashing techniques such as rolling hashes.
Understanding of binary search over a valid answer space to optimize problem-solving.
Skill in managing multiple paths and confirming common subpaths through set intersection.

Common Pitfalls or Variants

Common pitfalls

Failing to optimize the subpath verification process, leading to excessive brute-force comparisons.
Misunderstanding the relationship between binary search and subpath verification, resulting in inefficient solution design.
Overlooking edge cases, such as paths that are entirely distinct or paths with minimal overlap.

Follow-up variants

What if paths can contain repeated cities in non-consecutive order?
Can this solution be optimized further for large n and m values?
How would the solution change if we needed to find the longest common subpath across only a subset of the paths?

FAQ

What is the pattern to solve the Longest Common Subpath problem?

The problem can be efficiently solved using binary search over subpath lengths combined with rolling hashes to verify the presence of common subpaths.

How do I handle large inputs in the Longest Common Subpath problem?

For large inputs, it's important to optimize the subpath verification process using efficient algorithms like rolling hashes and minimize the number of comparisons with binary search.

What if there is no common subpath in the Longest Common Subpath problem?

If no common subpath exists, the solution will return 0, indicating that the friends' paths do not share any common subpath.

How do rolling hashes work in the Longest Common Subpath problem?

Rolling hashes allow you to compute hashes for subpaths in constant time as you slide over the paths, making it efficient to compare subpaths across different paths.

How does binary search help in the Longest Common Subpath problem?

Binary search is used to efficiently narrow down the possible lengths of the longest common subpath, reducing the number of candidate lengths to check.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

class Solution:
    def longestCommonSubpath(self, n: int, paths: List[List[int]]) -> int:
        def check(k: int) -> bool:
            cnt = Counter()
            for h in hh:
                vis = set()
                for i in range(1, len(h) - k + 1):
                    j = i + k - 1
                    x = (h[j] - h[i - 1] * p[j - i + 1]) % mod
                    if x not in vis:
                        vis.add(x)
                        cnt[x] += 1
            return max(cnt.values()) == m

        m = len(paths)
        mx = max(len(path) for path in paths)
        base = 133331
        mod = 2**64 + 1
        p = [0] * (mx + 1)
        p[0] = 1
        for i in range(1, len(p)):
            p[i] = p[i - 1] * base % mod
        hh = []
        for path in paths:
            k = len(path)
            h = [0] * (k + 1)
            for i, x in enumerate(path, 1):
                h[i] = h[i - 1] * base % mod + x
            hh.append(h)
        l, r = 0, min(len(path) for path in paths)
        while l < r:
            mid = (l + r + 1) >> 1
            if check(mid):
                l = mid
            else:
                r = mid - 1
        return l

Continue Practicing

#2223 sum of scores of built strings #1044 longest duplicate substring #718 maximum length of repeated subarray