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.
See Also: Weekly Contest 248
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 <= 105m == paths.length2 <= m <= 105sum(paths[i].length) <= 1050 <= 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[0]=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
seen.add(key)
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 loProgram 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[0].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);
nextNode.pathsSeen.add(shortestPathNum);
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;
nextNode.pathsSeen.add(pathNum);
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<>();
}
}
