The "Longest Common Subpath" problem asks you to determine the length of the longest path (as a sequence of city IDs) that appears as a contiguous subpath in every given path. Each path is an array of integers representing cities visited in order. The goal is to find the maximum length k such that there exists a sequence of k consecutive cities present in all the input paths.
k of a common subpath.At first glance, the problem seems to invite a brute-force approach: try all possible subpaths for one path and check if they appear in all others. However, with potentially large input sizes, this would be far too slow.
To optimize, we need to efficiently check whether a subpath of a certain length exists in all paths. This is a classic scenario for binary search: if a subpath of length k exists, then so does any shorter length. So, we can binary search on the possible length of the subpath.
But how do we check efficiently if a subpath of length k exists in all paths? We need a fast way to compare subpaths, which leads us to hashing techniques. By using a rolling hash (like Rabin-Karp), we can quickly hash all subpaths of length k in each path and check for common hashes.
left be 0 and right be the minimum path length among all paths.mid, check if there is a common subpath of length mid in all paths.mid.k for which a common subpath exists in all paths.Suppose we have the following input:
[[1,2,3,4], [2,3,4], [3,4,5]]mid = 2:
mid = 3:
n be the number of paths, m the minimum path length, and L the total length of all paths.O(\log m) iterations.k in each path: O(L) per iteration.O(L \cdot \log m).O(L) for storing hashes.The Longest Common Subpath problem is efficiently solved by combining binary search and rolling hash. Binary search narrows down the candidate subpath length, and rolling hash allows us to compare subpaths quickly across all paths. By intersecting sets of hashed subpaths, we determine the existence of a common subpath. This approach is both time and space efficient, making it suitable for large input sizes and demonstrating the power of combining classic algorithmic techniques.
class Solution:
def longestCommonSubpath(self, n, paths):
def check(length):
MOD = (1 << 61) - 1
BASE = 10**5 + 7
common = None
for idx, path in enumerate(paths):
h, power = 0, 1
hashes = set()
for i in range(length):
h = (h * BASE + path[i]) % MOD
if i < length - 1:
power = (power * BASE) % MOD
hashes.add(h)
for i in range(length, len(path)):
h = (h - path[i - length] * power) % MOD
h = (h * BASE + path[i]) % MOD
hashes.add(h)
if common is None:
common = hashes
else:
common = common & hashes
if not common:
return False
return True
left, right = 0, min(len(p) for p in paths)
while left < right:
mid = (left + right + 1) // 2
if check(mid):
left = mid
else:
right = mid - 1
return left
class Solution {
public:
int longestCommonSubpath(int n, vector<vector<int>>& paths) {
auto check = [&](int len) {
const long long MOD = (1LL << 61) - 1;
const long long BASE = 100007;
unordered_set<long long> common;
for (int idx = 0; idx < paths.size(); ++idx) {
long long h = 0, power = 1;
unordered_set<long long> hashes;
for (int i = 0; i < len; ++i) {
h = (h * BASE + paths[idx][i]) % MOD;
if (i < len - 1) power = (power * BASE) % MOD;
}
hashes.insert(h);
for (int i = len; i < paths[idx].size(); ++i) {
h = (h - paths[idx][i - len] * power % MOD + MOD) % MOD;
h = (h * BASE + paths[idx][i]) % MOD;
hashes.insert(h);
}
if (idx == 0) {
common = hashes;
} else {
unordered_set<long long> temp;
for (auto x : hashes) {
if (common.count(x)) temp.insert(x);
}
common = temp;
}
if (common.empty()) return false;
}
return true;
};
int left = 0, right = INT_MAX;
for (auto& path : paths) right = min(right, (int)path.size());
while (left < right) {
int mid = (left + right + 1) / 2;
if (check(mid)) left = mid;
else right = mid - 1;
}
return left;
}
};
class Solution {
public int longestCommonSubpath(int n, int[][] paths) {
long MOD = (1L << 61) - 1;
long BASE = 100007;
int minLen = Integer.MAX_VALUE;
for (int[] path : paths) minLen = Math.min(minLen, path.length);
int left = 0, right = minLen;
while (left < right) {
int mid = (left + right + 1) / 2;
if (check(paths, mid, BASE, MOD)) left = mid;
else right = mid - 1;
}
return left;
}
private boolean check(int[][] paths, int len, long BASE, long MOD) {
Set<Long> common = null;
for (int[] path : paths) {
long h = 0, power = 1;
Set<Long> hashes = new HashSet<>();
for (int i = 0; i < len; ++i) {
h = (h * BASE + path[i]) % MOD;
if (i < len - 1) power = (power * BASE) % MOD;
}
hashes.add(h);
for (int i = len; i < path.length; ++i) {
h = (h - path[i - len] * power % MOD + MOD) % MOD;
h = (h * BASE + path[i]) % MOD;
hashes.add(h);
}
if (common == null) {
common = hashes;
} else {
common.retainAll(hashes);
}
if (common.isEmpty()) return false;
}
return true;
}
}
var longestCommonSubpath = function(n, paths) {
function check(len) {
const MOD = BigInt((1n << 61n) - 1n);
const BASE = BigInt(100007);
let common = null;
for (const path of paths) {
let h = 0n, power = 1n;
const hashes = new Set();
for (let i = 0; i < len; ++i) {
h = (h * BASE + BigInt(path[i])) % MOD;
if (i < len - 1) power = (power * BASE) % MOD;
}
hashes.add(h.toString());
for (let i = len; i < path.length; ++i) {
h = (h - BigInt(path[i - len]) * power % MOD + MOD) % MOD;
h = (h * BASE + BigInt(path[i])) % MOD;
hashes.add(h.toString());
}
if (common === null) {
common = hashes;
} else {
common = new Set([...common].filter(x => hashes.has(x)));
}
if (common.size === 0) return false;
}
return true;
}
let left = 0, right = Math.min(...paths.map(p => p.length));
while (left < right) {
let mid = Math.floor((left + right + 1) / 2);
if (check(mid)) left = mid;
else right = mid - 1;
}
return left;
};