DP-14. Maximum Length of Repeated Subarray

Problem

718. Maximum Length of Repeated Subarray

Given two integer arrays A and B, return the maximum length of an subarray that appears in both arrays.

Example 1:
Input:
A: [1,2,3,2,1]
B: [3,2,1,4,7]
Output: 3
Explanation:
The repeated subarray with maximum length is [3, 2, 1].
Note:
1 <= len(A), len(B) <= 1000
0 <= A[i], B[i] < 100

Explanation

At first glance, I think maybe I can use two pointers, or actually, four pointers, however, that will be too complicated.

Then, look at the problem again. Isn’t is an optimal problem? So, we can use dynamic programming. As the this problem asks for subarray, so that would be simpler. As the current length of subarray is based on the previous length. We can make things simpler by starting from the end, which is known as bottom-up approach. dp[i][j] means a[i:] and b[j:] are repeated subarray. So, if the current a[i] == b[j], the dp[i][j] equals to dp[i+1][j+1] plus 1. Every time. we update the dp, we compare the maximum value and the dp to keep the maximum value.

Solution

Time complexity: O(MN), M,N is the length of A,B
Space complexity: O(M
N)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public int findLength(int[] a, int[] b) {
int res = 0;
int[][] dp = new int[a.length + 1][b.length + 1];

for (int i = a.length - 1; i >= 0; i--) {
for (int j = b.length - 1; j >= 0; j--) {
if (a[i] == b[j]) {
dp[i][j] = dp[i + 1][j + 1] + 1;
res = dp[i][j] > res ? dp[i][j] : res;
}
}
}
return res;
}
}