# Longest Common Subpath Leetcode Solution

Page Contents

## Longest Common Subpath

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.

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 = [,,]
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 , , , , and . 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]`.

## Solution

Program C++

Credit: HERE

Please note that we have to choose base wisely i.e. base >= 100007. Otherwise it’s just a simple rolling hash question. Also, the constraints of the problem were misleading during the contest.

``````#define ll long long

class Solution {
public:

ll base, MOD;
vector<ll> p;

bool works(ll len, vector<vector<int>>& paths, ll m){
unordered_set<ll> s;
for(ll i=0; i<m; i++){
if(paths[i].size()<len){
return false;
}
unordered_set<ll> ss;
ll hash=0;
for(ll j=0; j<len; j++){
hash=(hash+(((ll)(paths[i][j]+1)*p[len-1-j])%MOD))%MOD;
}
if(i==0){
s.insert(hash);
}
else{
if(s.find(hash)!=s.end()){
ss.insert(hash);
}
}
for(ll j=len; j<paths[i].size(); j++){
hash=(hash+MOD-(((ll)(paths[i][j-len]+1)*p[len-1])%MOD))%MOD;
hash=(ll)hash*base%MOD;
hash=(hash+paths[i][j]+1)%MOD;
if(i==0){
s.insert(hash);
}
else{
if(s.find(hash)!=s.end()){
ss.insert(hash);
}
}
}
if(i>0){
s=ss;
}
if(s.size()==0){
return false;
}
}
if(s.size()>0){
return true;
}
else{
return false;
}
}

int longestCommonSubpath(int n, vector<vector<int>>& paths) {
ll l=0, r=1e9L, m=paths.size();
base=100007, MOD=1e11L+7;
for(ll i=0; i<m; i++){
r=min(r, (ll)paths[i].size());
}
p=vector<ll>(r);
p=1;
for(ll i=1; i<r; i++){
p[i]=(ll)base*p[i-1]%MOD;
}
while(l<r){
ll mid=(l+r+1)/2;
if(works(mid, paths, m)){
l=mid;
}
else{
r=mid-1;
}
}
return r;
}
};``````

Program Python

``````class Solution:
def longestCommonSubpath(self, n: int, paths: List[List[int]]) -> int:
min_path = math.inf
for p in paths:
min_path = min(len(p), min_path)

def possible(guess):
index = Counter()
for p in paths:
seen = set()
for i in range(len(p)-guess+1):
key = tuple(p[i:i+guess])
if key not in seen:
index[key] += 1

if index[key] == len(paths):
return True
return False

lo, hi = 0, min_path
while lo < hi:
guess = (lo + hi + 1) // 2
if possible(guess):
lo = guess
else:
hi = guess - 1
return lo``````

Program Java

Credit: HERE

Build a trie in n^2 time using the smallest path. Then, test against the trie with the other paths in n^2 time each. Probably wont get below the time limit with this approach, but it is a different way to approach other than hashing.

``````class Solution {
public int longestCommonSubpath(int n, int[][] paths) {
TrieNode trie = new TrieNode();
int longestFull = 0;
int shortestPathNum = 0;
int shortestPathLength = paths.length;
for (int i = 0; i < paths.length; i++) {
if (paths[i].length < shortestPathLength) {
shortestPathLength = paths[i].length;
shortestPathNum = i;
}
}

// build Trie
for (int i = 0; i < paths[shortestPathNum].length; i++) {
TrieNode tempTrieNode = trie;
for (int j = i; j < paths[shortestPathNum].length; j++) {
int city = paths[shortestPathNum][j];
if (!tempTrieNode.next.containsKey(city)) tempTrieNode.next.put(city, new TrieNode());
TrieNode nextNode = tempTrieNode.next.get(city);
tempTrieNode = nextNode;
}
}

// test Trie
for (int pathNum = 0; pathNum < paths.length; pathNum++) {
if (pathNum == shortestPathNum) continue; // no need to test the builder
int[] path = paths[pathNum];
for (int i = 0; i < path.length; i++) {
TrieNode tempTrieNode = trie;
for (int j = i; j < path.length; j++) {
int city = path[j];
if (!tempTrieNode.next.containsKey(city)) break;
TrieNode nextNode = tempTrieNode.next.get(city);
if (nextNode.pathsSeen.size() < pathNum) break;
if (nextNode.pathsSeen.size() == paths.length) {
longestFull = Math.max(longestFull, j - i + 1);
}
tempTrieNode = nextNode;
}
}
}
return longestFull;
}

class TrieNode {
public Map<Integer, TrieNode> next = new HashMap<>();
public Set<Integer> pathsSeen = new HashSet<>();
}
}``````