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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Longest Common Subpath

Difficulty: Hard

Problem Description

There is a country of n cities numbered from 0 to n - 1. In this country, there is a road connecting every pair of cities. There are m friends who are traveling through the country, each taking a path represented by an integer array that contains the visited cities in order. The path may contain a city more than once, but the same city will not be listed consecutively. Given an integer n and a 2D integer array paths, where paths[i] is an integer array representing the path of the ith friend, return the length of the longest common subpath shared by every friend's path, or 0 if there is no common subpath at all.

Key Insights

  • A subpath is a contiguous sequence of cities within a path.
  • The problem requires finding the longest contiguous sequence that appears in all given paths.
  • Efficiently finding the longest common subpath can be achieved using a combination of binary search and rolling hash techniques.
  • Rolling hashes allow us to compute hash values for subarrays in constant time after an initial preprocessing step.

Space and Time Complexity

Time Complexity: O(m * (L + log L)), where L is the length of the longest path and m is the number of paths.
Space Complexity: O(m * L), where L is the length of the longest path.

Solution

To solve the problem, we can use a binary search to determine the maximum length of a common subpath. For each candidate length, we can use a rolling hash to compute the hashes of all subpaths of that length for each friend's path. We can store these hashes in a set to check for common hashes across all paths. If a common hash is found, it indicates that there is a common subpath of that length.

  1. Use binary search on the length of subpaths (from 1 to the length of the shortest path).
  2. For each length, generate hashes for subpaths using a rolling hash.
  3. Store the hashes of the first path in a set and check for matches with the hashes from subsequent paths.

Code Solutions

def longestCommonSubpath(n, paths):
    def check(length):
        # Rolling hash setup
        base = 10**5 + 3
        mod = 2**61 - 1
        curr_hash = 0
        base_l = 1
        hashes = set()

        for path in paths:
            seen = set()
            curr_hash = 0
            base_l = 1
            
            # Calculate the base^length % mod
            for i in range(length):
                curr_hash = (curr_hash * base + path[i]) % mod
                base_l = (base_l * base) % mod
                
            seen.add(curr_hash)

            for i in range(length, len(path)):
                curr_hash = (curr_hash * base + path[i] - path[i - length] * base_l) % mod
                seen.add(curr_hash)

            if not hashes:
                hashes = seen
            else:
                hashes.intersection_update(seen)

            if not hashes:
                return False
        
        return True

    left, right = 1, min(len(path) for path in paths)
    result = 0

    while left <= right:
        mid = (left + right) // 2
        if check(mid):
            result = mid
            left = mid + 1
        else:
            right = mid - 1

    return result
← Back to All Questions