Maximum Length of Repeated Subarray


The Python version of approach #2 doesn't get me "Time Limit Exceeded" but "Memory Limit Exceeded". I think it's fairly fast. I changed it to use strings, now it doesn't get MLE anymore. And it gets accepted in about 140 ms, which is faster than approaches #3 and #4 (which take about 2800 ms and
170 ms250 ms^{[*]}, respectively):def findLength(self, A, B): def check(length): seen = {A[i:i+length] for i in xrange(len(A)  length + 1)} return any(B[j:j+length] in seen for j in xrange(len(B)  length + 1)) A = ''.join(map(chr, A)) B = ''.join(map(chr, B)) lo, hi = 0, min(len(A), len(B)) + 1 while lo < hi: mi = (lo + hi) / 2 if check(mi): lo = mi + 1 else: hi = mi return lo  1
[*] The bug fix discussed below made it slower.

The implementation of Approach has some bug if there are two subarrays having the same hash value. In order to make the code 100% correct, we should define hashes as Map<Integer, List<Integer>>.
for (int x: rolling(A, guess)) { hashes.put(x, i++); // this has bug, should be something like hashes.put(x, new ArrayList<Integer>().add(i++); }
===========


I think O(1) space is enough for this problem :
see below post:
https://discuss.leetcode.com/topic/109751/javaomntimeo1space

This solution is O(M*N) in time, and O(min(M,N)) in space. It takes advantage of the fact that we don't need to rebuild the sequence when we're done, we only need to know the length. We also know that as we introduce new characters, we dont need to worry about results too far in the past, only the lengths of subarrays we found from the previous character:
class Solution { public: int findLength(vector<int>& A, vector<int>& B) { if(A.empty()  B.empty()) { return 0; } vector<int>* longer = &A; vector<int>* shorter = &B; if(A.size() < B.size()){ longer = &B; shorter = &A; } vector<short> dpt(shorter>size() + 1, 0); short * dp = &dpt[1]; short len = 0; for (const int v : *longer) { for (short i = shorter>size()  1; i >= 0 && len < shorter>size(); i) { if(v == (*shorter)[i]) { dp[i] = dp[i  1] + 1; if(dp[i] > len) { len = dp[i]; } } else { dp[i] = 0; } } } return len; } };

@StefanPochmann , for approach #2, by following the same in Java gets me accepted too . It looks like it may not work if this prerequisite is removed : 0 <= A[i], B[i] < 100 i.e. if any value is greater than 255.

@Chengcheng.Pei .Once you get a A[i] != B[j], the corresponding dp[i][j] will be 0(initialized) , then we start from 0 again.