Problem statement

https://leetcode.com/problems/maximum-length-of-repeated-subarray/

Solution 1

One way to solve this problem is to use dp approach, where dp[i][j] is the length of longest common suffix for A[:i] and B[:j]. Here we use trick that dp[-1][i] in the beginning is equal to zero. To evaluate dp[i][j] we just need to look at dp[i-1][j-1] if A[i] == B[j] and add one to it.

Complexity

Time and space complexity here is O(nm). Space complexity can be reduced to O(m) or O(n).

Code

class Solution(object):
    def findLength(self, A, B):
        n, m = len(A), len(B)
        dp = [[0] * (m + 1) for _ in range(n + 1)]
        for i in range(n):
            for j in range(m):
                if A[i] == B[j]:
                    dp[i][j] = dp[i-1][j-1]+1
        return max(max(row) for row in dp)

Solution 2

There is even better solution, using rolling hash: let us ask question if we have common subarray of length mid: Then we do binary search on this mid. Note that we can have collisions, so when we evaluate hashes, I go through all hashes and carefully check for each pair if we have common substring or not.

Complexity

For fixed mid we need O(min(m,n)), so overall complexity is O(log min(m,n) *(m+n)), space complexity is O(m+n). This is true if we assume that probability of collision is small enough and it is always matter of agreement in these type of approaches what we mean by small. Even though we say have 1 collision, complexity is still the same, because we need to do just additional comparison of strings.

Code

class Solution:
    def findLength(self, A, B):
        def RabinKarp(text, M):
            if M == 0: return {0: [0]}
            q = (1 << 31) - 1
            h, t, d = (1<<(8*M-8))%q, 0, 256

            dic = defaultdict(list)

            for i in range(M): 
                t = (d * t + text[i])% q

            dic[t].append(i-M+1)

            for i in range(len(text) - M):
                t = (d*(t-text[i]*h) + text[i + M])% q
                dic[t].append(i+1)
            return dic
        
        beg, end = 0, min(len(A), len(B)) + 1
        while beg + 1 < end:
            mid = (beg + end)//2
            d1, d2 = RabinKarp(A, mid), RabinKarp(B, mid)
            check = False
            for el in d1:
                l1, l2 = d1[el], d2[el]
                if any(A[q1:q1+mid]==B[q2:q2+mid] for q1, q2 in product(l1, l2)): check = True
                
            if check:
                beg = mid
            else:
                end = mid
        return beg

Remark

See also problem 1923. Longest Common Subpath, where you can apply rolling hash approach, but you can not apply dp approach. That is why I think it is important after you solved problem check discussion section and see if there are different ways to solve it and what are complexities.