We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Longest Common Subpath

Number: 2051

Difficulty: Hard

Paid? No

Companies: Amazon

Problem Description

Given n cities and m friends where each friend travels through some cities forming a path, find the length of the longest contiguous sequence of cities (subpath) that appears in every friend's path. If there is no common subpath, return 0.

Key Insights

  • Use binary search on the potential length of common subpaths.
  • For a fixed candidate length L, use rolling hash to efficiently compute and compare all subpaths of length L in each friend’s path.
  • Intersect the sets of hashes from all paths. If the intersection is non-empty, a common subpath of length L exists.
  • Using polynomial rolling hash reduces the time needed to check for common subpaths.
  • Since the total length of all paths is at most 10^5, the combination of binary search and rolling hash is efficient.

Space and Time Complexity

Time Complexity: O(total_length * log(min_path_length)) where total_length is the sum of the lengths of all paths. Space Complexity: O(total_length) for storing hash values and power arrays.

Solution

The solution applies a binary search over the possible subpath lengths. For each candidate length L:

  1. Compute the rolling hash values for every contiguous subpath of length L for each friend’s path.
  2. Store these hash values in a set.
  3. Intersect the sets from each friend. If at any candidate length L, the intersection is non-empty, then a common subpath of that length exists.
  4. Adjust the binary search range according to the presence/absence of a common subpath. The use of a rolling hash (with a proper base and modulus) allows quick computation of subpath hashes with O(1) sliding-window updates.

Code Solutions

# Python solution using binary search and rolling hash
def longestCommonSubpath(n, paths):
    MOD = (1 << 61) - 1  # A large prime modulus for rolling hash
    base = 100007      # A random base

    # Function to check if a common subpath of length L exists:
    def check(L):
        common = None  # Set of hashes common to all paths
        baseL = pow(base, L, MOD)
        for path in paths:
            if len(path) < L:
                return False
            current_set = set()
            h = 0
            # Calculate rolling hash for the first window of size L
            for i in range(L):
                h = (h * base + path[i]) % MOD
            current_set.add(h)
            # Slide the window and update hash
            for i in range(L, len(path)):
                h = (h * base - path[i - L] * baseL + path[i]) % MOD
                current_set.add(h)
            # Use intersection to narrow down common subpaths
            if common is None:
                common = current_set
            else:
                common = common.intersection(current_set)
            if not common:
                return False
        return True

    # Binary search for maximum length
    lo, hi = 0, min(len(p) for p in paths)
    ans = 0
    while lo <= hi:
        mid = (lo + hi) // 2
        if check(mid):
            ans = mid
            lo = mid + 1
        else:
            hi = mid - 1
    return ans

# Example usage:
n = 5
paths = [[0,1,2,3,4],
         [2,3,4],
         [4,0,1,2,3]]
print(longestCommonSubpath(n, paths))  # Output: 2
← Back to All Questions