1923. Longest Common Subpath

Problem Description

This problem is about finding the longest subpath that is common to every friend's travel path in a fully connected country. Here's the scenario in simple terms:

• There are n cities, and each city is connected to every other city.
• There are m friends, each with their travel paths represented as sequences of city numbers.
• The same city number can appear multiple times in a path, but not consecutively.
• A subpath is defined as a contiguous sequence of cities in a travel path.

The goal is to determine the length of the longest subpath that all friends' paths have in common. If no common subpath exists among all friends, the result should be 0.

Intuition

To solve this problem, we use a binary search to find the maximum length of a common subpath combined with rolling hash for subpath identification. To understand the intuition behind the solution, consider these steps:

1. Binary Search for Subpath Length: Since the subpath length can range from 0 to the length of the shortest path, we perform a binary search within this range. By finding the midpoint in each iteration, we can check if the current length exists as a subpath in all friends' paths. If it does, we try a longer length; if not, we shorten the search.

2. Rolling Hash to Compare Subpaths: To efficiently check if a subpath exists in all friends' paths, we use a rolling hash function. This computes a hash value for each subpath, which allows for constant-time comparison between subpaths.

3. Avoiding Hash Collisions: As we use modulo arithmetic with a large prime number to minimize hash collisions, the rolling hash function is less likely to give the same hash for different subpaths.

4. Using Counters: A Counter keeps track of how many times a particular hash appears in the list of subpaths of all friends' paths. If the count equals the number of friends (m), the subpath represented by that hash is common to all paths.

5. Deciding the Common Subpath Length: The binary search continues until we find the longest subpath length that appears in all friends' paths.

This method efficiently identifies the longest common subpath shared among every friend's path, by iteratively narrowing down the possible lengths and verifying existence using a consistent hashing technique.

Learn more about Binary Search patterns.

Solution Approach

The implementation of the solution uses function longestCommonSubpath, carrying out a binary search to zero in on the length of the longest common subpath. Here is a walkthrough of the method applied, revealing how algorithms, data structures, and patterns are put to use:

1. Pre-computation of Powers: Before executing the binary search, we compute powers of the base (base) used in the rolling hash function, storing them in an array p. The base is chosen as a large prime number for hash distribution. This pre-computation speeds up the subsequent hash calculations for different subpaths.

2. Rolling Hash Function: The function check(k) computes a rolling hash for each subpath of length k in each friend's path. This is achieved with the formula (h[j] - h[i - 1] * p[j - i + 1]) % mod, where h is the prefix hash array and mod is a large prime number for modulo operation to avoid overflow and collisions.

3. Counter for Hash Values: A Counter cnt is used to track how many times each hash appears across all paths. This counter helps identify if a hash, which represents a subpath of length k, is common to all friends' paths by comparing the count to the total number of friends m.

4. Using A Set to Avoid Duplicates: Inside check(k), a set vis is employed for each friend's path hashes to ensure the same subpath is not counted multiple times for a single friend, which would misrepresent the actual commonality of that subpath.

5. Binary Search: We initiate the binary search between 0 and the length of the shortest path (inclusive) to find the longest length k for which check(k) returns True. The condition in the binary search contrasts the max count value in cnt to m to determine if a common subpath of length k exists. If it is successful, we increase the lower boundary l to mid. Otherwise, we decrease the upper boundary r to mid - 1. We continue this process until l and r converge to the maximum value of k.

6. Returning the Result: After the binary search concludes, the variable l holds the length of the longest common subpath, which is the answer we return.

By leveraging the efficiency of binary search and the uniqueness of hash values produced by a rolling hash function, the function longestCommonSubpath determines the maximum length of a subpath common to all friends' paths with optimized time complexity.

Example Walkthrough

Let's illustrate the solution approach with a simple example:

Suppose we have 3 cities {1, 2, 3} and 2 friends with the following travel paths:

• Friend 1: {1, 2, 3, 2}
• Friend 2: {2, 3, 2, 1}

We are interested in finding the longest subpath that is common to every friend's travel path.

1. Pre-computation of Powers:

   • Assume our base for hashing is a prime number, let's say 101. We pre-compute the powers of this base up to the length of the shortest path (here both paths are of the same length, so we compute 4 powers).

2. Binary Search Initiation:

   • The range of possible subpath lengths is [0, 4]. We start with a binary search between these values.

3. First Iteration of Binary Search:

   • The mid-point of [0, 4] is 2, so we check for subpaths of length 2 (k = 2).

4. Rolling Hash Calculation:

   • Compute the rolling hash for each subpath of length 2 in both friends' paths:
     • Friend 1 would have subpaths {1, 2}, {2, 3}, {3, 2}.
     • Friend 2 would have subpaths {2, 3}, {3, 2}, {2, 1}.
   • Let's calculate an example hash with a fake hash function for demonstrating purposes (actual hashes would involve the precomputed powers and modulo operations to avoid collisions):
     • Hash for {1, 2} might be 5.
     • Hash for {2, 3} might be 11.
     • Hash for {3, 2} might be 11.
     • Hash for {2, 1} might be 8.
   • We notice that the subpath {2, 3} with hash 11 is common to both friends.

5. Counter Update and Set Utilization:

   • A counter cnt would count each unique hash per friend. Since hash 11 appears in both friends' paths and is the only one that does, it has the highest count, which is equal to the number of friends m = 2.
   • The set vis ensures that we only count {2, 3} once for Friend 1 although it appears twice.

6. Concluding the Binary Search:

   • Since we found a common subpath of the tested length 2, we now look for a longer common subpath by updating our binary search range to [3, 4].
   • Next mid-point is 3.5 (we consider 3 for subpath length). We repeat steps 4 and 5 for length 3:
     • Friend 1 would have subpaths {1, 2, 3} and {2, 3, 2}.
     • Friend 2 would have subpaths {2, 3, 2} and {3, 2, 1}.
     • No common subpaths of length 3 are found in both friends' paths.
   • Since there is no common subpath of length 3, we update our binary search range to [2, 2].

7. Returning the Result:

   • The binary search range [2, 2] indicates that the longest common subpath length is 2, which is the solution that the function longestCommonSubpath would return.

In this example, the longest common subpath that exists in both friends' paths is of length 2, and it consists of the sequence of cities {2, 3}. This example demonstrates how binary search, along with a rolling hash, can be used to efficiently find the longest common subpath among paths taken by different friends.

Solution Implementation

Time and Space Complexity

Time Complexity

The time complexity has several components derived from different parts of the code.

1. Initializing the power array p: This loop runs for mx+1 iterations, where mx is the length of the longest path in paths. So this part is O(mx).

2. Computing hashes for each path: For each path in paths (and there are m = len(paths) such paths), we calculate the prefix hash in a loop that runs for k + 1 iterations (k being the length of the individual path). The overall complexity for this part would be O(m*mx) since O(k+1) is bounded by the length of the longest path.

3. The binary search: The binary search runs O(log(mx)) times (mx being the maximum length of a path).

4. Inside the binary search, the check(k: int) function is called, which iterates over each of m paths and for each path goes through a loop of up to O(mx - k) iterations where mx is the maximum length of a path in paths and k the current guess for the binary search. But since we only add a hash to vis if it has not been seen before, and there are at most mx unique hashes, we can argue this costs O(mx) time per path. Since m paths are considered, each call to check function costs O(m*mx).

Combining these, the time complexity of the binary search dominates the overall time complexity. The total time complexity is O(m * mx * log(mx)).

Space Complexity

The space complexity of the code also comprises several parts:

1. The power array p consumes O(mx) space.

2. Storing hashes hh for each path takes O(m * mx), as for each of the m paths we store an array of hashes of length proportional to the path length mx.

3. The check function uses a Counter and a set, which in the worst-case could store up to O(mx) unique hashes for each path (across all paths in hh). Thus, the space needed may be up to O(mx).

Combining these parts, the dominant space complexity is from storing the hashes hh. Given this, the overall space complexity is O(m * mx).

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