LeetCode 718. Maximum Length of Repeated Subarray

Question

Given two integer arrays nums1 and nums2, return the maximum length of a subarray that appears in both arrays.

Example 1:

Input: nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
Output: 3
Explanation: The repeated subarray with maximum length is [3,2,1].

Example 2:

Input: nums1 = [0,0,0,0,0], nums2 = [0,0,0,0,0]
Output: 5

Constraints:

• 1 <= nums1.length, nums2.length <= 1000
• 0 <= nums1[i], nums2[i] <= 100

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

Solution

The key idea of the transition equation is that a long common string (array) must contain short common strings (arrays). Thus, a long common string can be grown from a short common string.

We simplify the searching process by searching common prefix num[i:], so that we only need to move one end of the string (array). Also, common suffix has the same effect.

// DP, prefix
public int findLength(int[] nums1, int[] nums2) {
    int len1 = nums1.length;
    int len2 = nums2.length;
    int maxCommonLen = 0;
    // dp[i][j] is the max length of common prefix of nums1[i:] and nums2[j:]
    // elements on the redundant row and column are initialized to zero, simplify the implementation
    int[][] dp = new int[len1 + 1][len2 + 1];
    for (int i = len1 - 1; i >= 0; i--) {
        for (int j = len2 - 1; j >= 0; j--) {
            if (nums1[i] == nums2[j]) {
                dp[i][j] = dp[i + 1][j + 1] + 1;
            } else {
                dp[i][j] = 0;
            }
            maxCommonLen = Math.max(maxCommonLen, dp[i][j]);
        }
    }
    return maxCommonLen;
}