Iram Shahed Iram Shahed - 1 month ago 7
Java Question

Finding the count of common array sequencce

I am trying to the length of the longest sequence of numbers shared by two arrays. Given the following two arrays:

int [] a = {1, 2, 3, 4, 6, 8,};
int [] b = {2, 1, 2, 3, 5, 6,};


The result should be
3
as the the longest common sequence between the two is
{1, 2, 3}
.
The numbers must be in a sequence for the program to consider to count it.
I have thought about it and wrote a small beginning however, I am not sure how to approach this

public static int longestSharedSequence(int[] arr, int[] arr2){
int start = 0;
for(int i = 0; i < arr.length; i++){
for(int j = 0; j < arr2.length; j++){
int n = 0;
while(arr[i + n] == arr2[j + n]){
n++;
if(((i + n) >= arr.length) || ((j + n) >= arr2.length)){
break;
}
}
}

Answer

That is a very good start that you have. All you need to do is have some way of keeping track of the best n value that you have encountered. So at the start of the method, declare int maxN = 0. Then, after the while loop within the two for loops, check if n (the current matching sequence length) is greater than maxN (the longest matching sequence length encountered so far). If so, update maxN to the value of n.

Since you also want the matching elements to be in sequential order, you will need to check that the elements in the two arrays not only match, but that they are also 1 greater than the previous element in each array. Putting these together gives the following code:

public static int longestSharedSequence(int[] arr, int[] arr2) {
    int maxN = 0;
    for (int i = 0; i < arr.length; i++) {
        for (int j = 0; j < arr2.length; j++) {
            int n = 0;
            // Check that elements match and that they are either the
            // first element in the sequence that is currently being
            // compared or that they are 1 greater than the previous
            // element
            while (arr[i + n] == arr2[j + n]
                    && (n == 0 || arr[i + n] == arr[i + n - 1] + 1)) {
                n++;
                if (i + n >= arr.length || j + n >= arr2.length) {
                    break;
                }
            }

            // If we found a longer sequence than the previous longest,
            // update maxN
            if (n > maxN) {
                maxN = n;
            }
        }
    }
    return maxN;
}