# Longest Common Subpath
**Difficulty:** HARD
[External](https://leetcode.com/problems/longest-common-subpath)
Canonical: https://scaleengineer.com/dsa/problems/longest-common-subpath
**Patterns:** [Rolling Hash](https://scaleengineer.com/dsa/patterns/rolling-hash), [Hash Function](https://scaleengineer.com/dsa/patterns/hash-function)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Data structures:** Array, Suffix Array
---
## Problem
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 numbered from `0` to `m - 1` who are traveling through the country. Each one of them will take a path consisting of some cities. Each path is 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** that is shared by **every** friend's path, or_ `0` _if there is no common subpath at all_.

A **subpath** of a path is a contiguous sequence of cities within that path.

**Example 1:**

**Input:** n = 5, paths = [[0,1,2,3,4],
                       [2,3,4],
                       [4,0,1,2,3]]
**Output:** 2
**Explanation:** The longest common subpath is [2,3].

**Example 2:**

**Input:** n = 3, paths = [[0],[1],[2]]
**Output:** 0
**Explanation:** 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
**Explanation:** 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]`.

# Approaches
## Brute Force by Checking All Subpaths
This approach is a straightforward, brute-force method. The core idea is to generate all possible candidate subpaths from one of the paths and then verify if each candidate exists in all other paths. To slightly optimize, we can choose the shortest path to generate candidates from, as it has the fewest subpaths. We check for the longest possible subpaths first and decrease the length, so the first common subpath found will be the longest.
**Time:** O(L_s^2 * L_total * L_s), where `L_s` is the length of the shortest path and `L_total` is the sum of all path lengths. This is a rough estimate, but it's a high-degree polynomial in the path lengths and will result in a 'Time Limit Exceeded' error on the given constraints. · **Space:** O(L_s), where `L_s` is the length of the shortest path. This space is used to store a single candidate subpath.
**Pros:** Simple to conceptualize and implement.; Requires minimal auxiliary data structures.
**Cons:** Extremely high time complexity, making it infeasible for the given constraints.; Repeatedly scans paths, leading to a lot of redundant computations.
### Explanation
The algorithm begins by identifying the shortest path to minimize the number of subpaths we need to check. Then, it iterates from the maximum possible length (the length of this shortest path) down to 1. In each iteration, it extracts all subpaths of the current length from the shortest path. For each of these subpaths, it performs a search across all the other paths to see if it's a common subpath. This verification is done by a simple linear scan. The first length for which a common subpath is found is the answer.

```java
class Solution {
    public int longestCommonSubpath(int n, int[][] paths) {
        if (paths == null || paths.length == 0) {
            return 0;
        }

        // Find the shortest path to optimize a bit
        int shortestPathIdx = 0;
        for (int i = 1; i < paths.length; i++) {
            if (paths[i].length < paths[shortestPathIdx].length) {
                shortestPathIdx = i;
            }
        }
        
        int[] shortestPath = paths[shortestPathIdx];

        for (int len = shortestPath.length; len >= 1; len--) {
            // Generate all subpaths of length 'len' from the shortest path
            for (int i = 0; i <= shortestPath.length - len; i++) {
                int[] subpath = new int[len];
                System.arraycopy(shortestPath, i, subpath, 0, len);

                boolean isCommon = true;
                // Check if this subpath exists in all other paths
                for (int j = 0; j < paths.length; j++) {
                    if (!containsSubpath(paths[j], subpath)) {
                        isCommon = false;
                        break;
                    }
                }

                if (isCommon) {
                    return len; // Found the longest
                }
            }
        }

        return 0;
    }

    // Helper to check if a path contains a subpath
    private boolean containsSubpath(int[] path, int[] subpath) {
        for (int i = 0; i <= path.length - subpath.length; i++) {
            boolean match = true;
            for (int j = 0; j < subpath.length; j++) {
                if (path[i + j] != subpath[j]) {
                    match = false;
                    break;
                }
            }
            if (match) {
                return true;
            }
        }
        return false;
    }
}
```
### Algorithm
1. Find the path with the minimum length. Let's call it `shortestPath`.
2. Iterate through all possible subpath lengths `L`, from `shortestPath.length` down to 1.
3. For each length `L`, generate all subpaths of `shortestPath`.
4. For each generated `subpath`:
    a. Assume it's a common subpath (`isCommon = true`).
    b. Iterate through all other paths in `paths`.
    c. Check if `subpath` exists in the current path using a naive linear scan.
    d. If it doesn't exist, set `isCommon = false` and break the inner loop.
5. If after checking all other paths `isCommon` is still true, it means we have found the longest common subpath of length `L`. Return `L`.
6. If the loops complete, no common subpath was found. Return 0.

## Binary Search on Length with Rabin-Karp
This efficient approach combines binary search on the answer with the Rabin-Karp string searching algorithm. The length of the longest common subpath is found by binary searching in the range of possible lengths. For a given length `k`, we need an efficient way to check if a common subpath of that length exists across all paths. This check is performed using rolling hashes. We compute the hashes of all subpaths of length `k` for the first path and then iteratively filter these hashes by checking for their presence in the subsequent paths. If any hashes remain after checking all paths, a common subpath of length `k` exists.
**Time:** O(L_total * log(L_s)), where `L_total` is the sum of the lengths of all paths and `L_s` is the length of the shortest path. The `check` function takes O(L_total) time, and it's called O(log(L_s)) times by the binary search. · **Space:** O(L_s), where `L_s` is the length of the shortest path. This space is required to store the hashes of the subpaths of the shortest path.
**Pros:** Very efficient, with a time complexity suitable for the given constraints.; The combination of binary search and rolling hash is a powerful and standard technique for solving problems involving finding an optimal-length common substring/subarray.
**Cons:** More complex to implement than brute force.; Requires careful implementation of the rolling hash to avoid bugs (e.g., handling modular arithmetic correctly).; Hash collisions are possible, though unlikely with good hash functions (using two independent hash functions is a robust way to mitigate this).
### Explanation
The solution binary searches for the longest possible length `k`. The `check(k)` function is the core of this approach.

To implement `check(k)`, we use a rolling hash to represent each subpath of length `k` as a single number. This allows for fast comparisons and storage in a hash set.

1.  **Hashing:** We pick a base and a large prime modulus. The hash for a subpath `p[0...k-1]` is `(p[0]*base^(k-1) + p[1]*base^(k-2) + ... + p[k-1]) % mod`. The hash for the next window `p[1...k]` can be calculated from the previous hash in O(1) time.
2.  **Intersection:** We start by calculating all subpath hashes for the shortest path and storing them in a set. Then, for each of the other paths, we calculate their subpath hashes and perform a set intersection with our set of common hashes. If the set becomes empty, we know no common subpath of length `k` exists.

This process is repeated within the binary search until the optimal length is found.

```java
import java.util.*;

class Solution {
    // Using one hash function for simplicity, but two are recommended for robustness.
    // Base should be greater than the max value of a city id (n).
    private static final long BASE = 100001;
    private static final long MOD = 1_000_000_007;

    public int longestCommonSubpath(int n, int[][] paths) {
        int minLen = Integer.MAX_VALUE;
        int shortestPathIdx = 0;
        for (int i = 0; i < paths.length; i++) {
            if (paths[i].length < minLen) {
                minLen = paths[i].length;
                shortestPathIdx = i;
            }
        }

        // Move the shortest path to the front to optimize space for the hash set.
        int[] temp = paths[0];
        paths[0] = paths[shortestPathIdx];
        paths[shortestPathIdx] = temp;

        int low = 0, high = minLen, ans = 0;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (mid == 0) {
                low = mid + 1;
                continue;
            }
            if (check(mid, paths)) {
                ans = mid;
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return ans;
    }

    private boolean check(int len, int[][] paths) {
        Set<Long> commonHashes = calculateHashes(paths[0], len);
        if (commonHashes.isEmpty()) return false;

        for (int i = 1; i < paths.length; i++) {
            Set<Long> currentPathHashes = calculateHashes(paths[i], len);
            commonHashes.retainAll(currentPathHashes);
            if (commonHashes.isEmpty()) {
                return false;
            }
        }
        return true;
    }

    private Set<Long> calculateHashes(int[] path, int len) {
        Set<Long> hashes = new HashSet<>();
        if (path.length < len) return hashes;

        long hash = 0;
        long power = 1; // To store BASE^(len-1)

        // Calculate hash of the first window and the highest power of BASE
        for (int i = 0; i < len; i++) {
            hash = (hash * BASE + (path[i] + 1)) % MOD;
            if (i < len - 1) {
                power = (power * BASE) % MOD;
            }
        }
        hashes.add(hash);

        // Roll the hash for subsequent windows
        for (int i = len; i < path.length; i++) {
            long prevTerm = ((long)(path[i - len] + 1) * power) % MOD;
            hash = (hash - prevTerm + MOD) % MOD; // Remove leading term
            hash = (hash * BASE + (path[i] + 1)) % MOD; // Add trailing term
            hashes.add(hash);
        }
        return hashes;
    }
}
```
### Algorithm
1. The problem has a monotonic property: if a common subpath of length `k` exists, a common subpath of length `k-1` also exists. This allows for binary searching on the answer (the length).
2. Set up a binary search range for the length, from `low = 0` to `high = min_len`, where `min_len` is the length of the shortest path.
3. In each step of the binary search, check if a common subpath of length `mid = low + (high - low) / 2` exists using a helper function, `check(mid)`.
4. If `check(mid)` is true, it means length `mid` is possible. We try for a longer path: `ans = mid`, `low = mid + 1`.
5. If `check(mid)` is false, `mid` is too long. We search for a shorter path: `high = mid - 1`.
6. The `check(k)` function uses the Rabin-Karp algorithm with rolling hashes:
    a. Generate all rolling hashes for subpaths of length `k` in the first path (ideally the shortest one) and store them in a `HashSet` called `commonHashes`.
    b. For each subsequent path, generate its subpath hashes and find the intersection with `commonHashes`. Update `commonHashes` with the result.
    c. If `commonHashes` becomes empty at any point, return `false`.
    d. If the loop completes and `commonHashes` is not empty, return `true`.

# Solutions
### Java

```java
class Solution {
  int N = 100010;
  long[] h = new long[N];
  long[] p = new long[N];
private
  int[][] paths;
  Map<Long, Integer> cnt = new HashMap<>();
  Map<Long, Integer> inner = new HashMap<>();
public
  int longestCommonSubpath(int n, int[][] paths) {
    int left = 0, right = N;
    for (int[] path : paths) {
      right = Math.min(right, path.length);
    }
    this.paths = paths;
    while (left < right) {
      int mid = (left + right + 1) >> 1;
      if (check(mid)) {
        left = mid;
      } else {
        right = mid - 1;
      }
    }
    return left;
  }
private
  boolean check(int mid) {
    cnt.clear();
    inner.clear();
    p[0] = 1;
    for (int j = 0; j < paths.length; ++j) {
      int n = paths[j].length;
      for (int i = 1; i <= n; ++i) {
        p[i] = p[i - 1] * 133331;
        h[i] = h[i - 1] * 133331 + paths[j][i - 1];
      }
      for (int i = mid; i <= n; ++i) {
        long val = get(i - mid + 1, i);
        if (!inner.containsKey(val) || inner.get(val) != j) {
          inner.put(val, j);
          cnt.put(val, cnt.getOrDefault(val, 0) + 1);
        }
      }
    }
    int max = 0;
    for (int val : cnt.values()) {
      max = Math.max(max, val);
    }
    return max == paths.length;
  }
private
  long get(int l, int r) { return h[r] - h[l - 1] * p[r - l + 1]; }
}

```

### Python

```python
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

```