Problem Description

You have a country with n cities numbered from 0 to n - 1. Every pair of cities in this country is connected by a road.

There are m friends (numbered from 0 to m - 1) traveling through the country. Each friend follows a specific path through the cities, represented as an array of city numbers in the order they visit them. A friend can visit the same city multiple times in their journey, but the same city won't appear consecutively in their path.

Given:

• An integer n (number of cities)
• A 2D array paths where paths[i] represents the travel path of the i-th friend

Your task is to find the length of the longest common subpath that appears in every friend's path. If no common subpath exists among all friends, return 0.

A subpath is defined as a contiguous sequence of cities within a path. For example, if a friend's path is [1, 2, 3, 4], then [2, 3] is a subpath, but [1, 3] is not (since it's not contiguous).

The solution uses binary search combined with rolling hash to efficiently find the longest common subpath. The algorithm:

1. Binary searches on the possible length of the common subpath (from 0 to the minimum path length)
2. For each candidate length k, uses rolling hash to check if there exists a subpath of length k that appears in all friends' paths
3. The rolling hash technique allows checking all subpaths of a given length in linear time by computing hash values incrementally
4. Returns the maximum length where a common subpath exists among all friends

Intuition

The key insight is recognizing that if a common subpath of length k exists among all friends' paths, then any common subpath of length less than k also exists. This monotonic property makes binary search applicable.

Think about it this way: if all friends share the subpath [2, 3, 4] (length 3), then they definitely also share [2, 3] (length 2) and [3, 4] (length 2). This means we can binary search on the length of the common subpath.

The challenge then becomes: given a specific length k, how do we efficiently check if there's a common subpath of that length?

A naive approach would be to extract all subpaths of length k from each friend's path and find their intersection. However, comparing subpaths directly would be expensive - for each subpath comparison, we'd need O(k) time to check if two sequences are equal.

This is where rolling hash comes in. Instead of comparing subpaths element by element, we compute a hash value for each subpath. The hash function is designed so that:

1. Equal subpaths always produce the same hash value
2. We can compute the hash of adjacent subpaths incrementally in O(1) time

The rolling hash formula used is: for a subpath [a, b, c], the hash is a * base^2 + b * base^1 + c * base^0. When we slide the window to get the next subpath, we can update the hash value by removing the contribution of the leftmost element and adding the new rightmost element.

To check if a subpath of length k is common to all friends:

1. For each friend's path, compute hashes of all subpaths of length k
2. Track which unique subpath hashes each friend has seen (using a set to avoid counting the same subpath multiple times per friend)
3. Count how many friends have seen each unique hash
4. If any hash appears in all m friends' paths, then a common subpath of length k exists

The binary search narrows down the maximum possible length, ultimately finding the longest common subpath shared by all friends.

Learn more about Binary Search patterns.

Solution Approach

The solution implements a binary search combined with rolling hash to find the longest common subpath efficiently.

Step 1: Preprocessing - Computing Hash Arrays

First, we precompute powers of the base for the rolling hash:

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

Then, for each friend's path, we compute a prefix hash array:

for path in paths:
    h = [0] * (len(path) + 1)
    for i, x in enumerate(path, 1):
        h[i] = h[i - 1] * base % mod + x
    hh.append(h)

The prefix hash allows us to compute the hash of any subpath [i, j] in O(1) time using the formula: hash(i, j) = (h[j] - h[i-1] * p[j-i+1]) % mod

Step 2: Binary Search on Length

We binary search on the possible length of the common subpath:

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

The search range is from 0 to the length of the shortest path (since the common subpath can't be longer than any individual path).

Step 3: Checking if Length k is Valid

The check(k) function determines if there exists a common subpath of length k:

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

For each friend's path:

1. We iterate through all possible starting positions for a subpath of length k
2. Calculate the hash value of each subpath using the rolling hash formula
3. Use a set vis to track unique subpath hashes for this friend (avoiding duplicate counts)
4. Increment the global counter cnt for each unique hash

If any hash value appears exactly m times (once for each friend), then all friends share that subpath.

Time Complexity:

• Preprocessing: O(total_path_length) to compute all prefix hashes
• Each check(k) call: O(total_path_length) to examine all subpaths
• Binary search makes O(log(min_path_length)) calls to check
• Overall: O(total_path_length * log(min_path_length))

Space Complexity:

• O(total_path_length) for storing the prefix hash arrays
• O(number_of_unique_subpaths) for the hash counter and visited sets

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Input:

• n = 5 (cities numbered 0-4)
• paths = [[0,1,2,3,4], [2,3,4], [4,0,1,2,3]]
• We have 3 friends with their respective paths

Step 1: Preprocessing - Computing Hash Arrays

First, we compute the prefix hash arrays for each path. Let's use base = 10 for simplicity (actual solution uses 133331):

For path [0,1,2,3,4]:

• h[0] = 0
• h[1] = 0*10 + 0 = 0
• h[2] = 0*10 + 1 = 1
• h[3] = 1*10 + 2 = 12
• h[4] = 12*10 + 3 = 123
• h[5] = 123*10 + 4 = 1234

Similarly compute for [2,3,4] and [4,0,1,2,3].

Step 2: Binary Search on Length

The minimum path length is 3 (friend 1's path), so we binary search between 0 and 3.

First iteration: l=0, r=3, mid=2 Check if there's a common subpath of length 2.

Step 3: Checking Length 2

For each friend's path, extract all subpaths of length 2 and compute their hashes:

Friend 0's path [0,1,2,3,4]:

• [0,1]: hash = 0*10 + 1 = 1
• [1,2]: hash = 1*10 + 2 = 12
• [2,3]: hash = 2*10 + 3 = 23
• [3,4]: hash = 3*10 + 4 = 34

Friend 1's path [2,3,4]:

• [2,3]: hash = 2*10 + 3 = 23
• [3,4]: hash = 3*10 + 4 = 34

Friend 2's path [4,0,1,2,3]:

• [4,0]: hash = 4*10 + 0 = 40
• [0,1]: hash = 0*10 + 1 = 1
• [1,2]: hash = 1*10 + 2 = 12
• [2,3]: hash = 2*10 + 3 = 23

Count occurrences:

• Hash 1: appears in 2 friends (0,2)
• Hash 12: appears in 2 friends (0,2)
• Hash 23: appears in 3 friends (0,1,2) ✓
• Hash 34: appears in 2 friends (0,1)
• Hash 40: appears in 1 friend (2)

Since hash 23 (representing subpath [2,3]) appears in all 3 friends' paths, check(2) returns true.

Binary search continues: l=2, r=3, mid=3

Checking Length 3:

Friend 0's path [0,1,2,3,4]:

• [0,1,2]: hash = 12
• [1,2,3]: hash = 123
• [2,3,4]: hash = 234

Friend 1's path [2,3,4]:

• [2,3,4]: hash = 234

Friend 2's path [4,0,1,2,3]:

• [4,0,1]: hash = 401
• [0,1,2]: hash = 12
• [1,2,3]: hash = 123

Count occurrences:

• Hash 12: appears in 2 friends (0,2)
• Hash 123: appears in 2 friends (0,2)
• Hash 234: appears in 2 friends (0,1)
• Hash 401: appears in 1 friend (2)

No hash appears in all 3 friends' paths, so check(3) returns false.

Binary search updates: r=2

Since l=2 and r=2, the search terminates.

Result: The longest common subpath has length 2, which corresponds to [2,3] that all friends visit in their journeys.

Solution Implementation

Time and Space Complexity

Time Complexity: O(S * log(min_len)) where S is the total sum of all path lengths and min_len is the length of the shortest path.

The analysis breaks down as follows:

• Binary search runs for O(log(min_len)) iterations
• For each binary search iteration, we call the check(k) function
• Inside check(k):
  • We iterate through all m paths
  • For each path of length len(path), we compute rolling hashes for all subpaths of length k, which takes O(len(path) - k + 1) iterations
  • Each hash computation is O(1) due to the precomputed prefix hashes
  • Total work in check(k) is O(sum(len(path) - k + 1)) for all paths, which is O(S)
• Preprocessing step computes prefix hashes for all paths in O(S) time
• Overall: O(S) + O(S * log(min_len)) = O(S * log(min_len))

Space Complexity: O(S + mx) where S is the total sum of all path lengths and mx is the length of the longest path.

The space breakdown:

• Array p stores powers of base up to mx + 1: O(mx)
• Array hh stores prefix hashes for all paths: O(S) total space
• Inside check(k):
  • cnt Counter can store at most O(S) unique hash values
  • vis set for each path stores at most O(len(path)) hashes
• Overall: O(S + mx)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Hash Collision Issues with Poor Hash Function Choice

Pitfall: Using a small modulo or inappropriate base value can lead to hash collisions, where different subpaths produce the same hash value. This causes the algorithm to incorrectly identify non-matching subpaths as identical.

Example scenario:

• Using MOD = 10^9 + 7 (a common choice) might cause collisions when dealing with large datasets
• Using a small base like 31 or 256 increases collision probability

Solution:

• Use a large prime modulo like 2^64 + 1 or 2^61 - 1
• Choose a large random prime base (e.g., 133331)
• Consider using double hashing with two different hash functions for extra safety:

def has_common_subpath_with_double_hash(length: int) -> bool:
    BASE1, MOD1 = 133331, 2**64 + 1
    BASE2, MOD2 = 100003, 2**61 - 1
  
    hash_count = Counter()
  
    for i, path in enumerate(paths):
        seen_hashes = set()
      
        for start in range(len(path) - length + 1):
            # Compute two independent hashes
            hash1 = compute_hash(path, start, length, BASE1, MOD1)
            hash2 = compute_hash(path, start, length, BASE2, MOD2)
            combined_hash = (hash1, hash2)  # Use tuple as key
          
            if combined_hash not in seen_hashes:
                seen_hashes.add(combined_hash)
                hash_count[combined_hash] += 1
  
    return max(hash_count.values()) == num_paths

2. Incorrect Handling of Duplicate Subpaths Within a Single Path

Pitfall: Counting the same subpath multiple times within a single friend's path, leading to incorrect results when checking if a subpath appears in all paths.

Example: If friend 0's path is [1, 2, 3, 1, 2] and we're checking for subpath [1, 2], it appears twice. Without proper deduplication, the counter might show this subpath appearing "2 times" when we only have 1 friend.

Solution: The code correctly handles this by using a seen_hashes set for each path to ensure each unique subpath is counted only once per friend:

seen_hashes = set()  # Reset for each friend's path
for start_idx in range(1, len(path_hash) - length + 1):
    # ... calculate subpath_hash ...
    if subpath_hash not in seen_hashes:  # Only count once per path
        seen_hashes.add(subpath_hash)
        hash_count[subpath_hash] += 1

3. Off-by-One Errors in Index Calculations

Pitfall: Confusion between 0-based and 1-based indexing when computing prefix hashes and extracting subpath hashes.

Common mistakes:

• Using wrong range boundaries: range(0, len(path_hash) - length) instead of range(1, len(path_hash) - length + 1)
• Incorrect power calculation: using base_powers[length] instead of base_powers[end_idx - start_idx + 1]

Solution: Be consistent with indexing convention. The code uses 1-based indexing for prefix hashes:

# Prefix hash array is 1-indexed: prefix_hash[i] = hash of path[0:i]
for i, city in enumerate(path, 1):  # Start from index 1
    prefix_hash[i] = (prefix_hash[i - 1] * BASE + city) % MOD

# When extracting subpath hash, adjust indices accordingly
for start_idx in range(1, len(path_hash) - length + 1):  # 1-based start
    end_idx = start_idx + length - 1
    # Use the correct power: end_idx - start_idx + 1 = length
    subpath_hash = (path_hash[end_idx] - path_hash[start_idx - 1] * base_powers[length]) % MOD

4. Integer Overflow in Languages Without Arbitrary Precision

Pitfall: In languages like C++ or Java, multiplying large numbers can cause integer overflow before the modulo operation is applied.

Solution for other languages:

// C++ solution using unsigned long long and careful modulo
unsigned long long computeHash(int start, int length) {
    // Use multiplication with modulo at each step
    unsigned long long hash = (prefixHash[start + length] - 
                              (prefixHash[start] * power[length] % MOD) + MOD) % MOD;
    return hash;
}

In Python, this isn't an issue due to arbitrary precision integers, but it's important to be aware of when porting the solution.