Check if a sequence of items in an array is repeating

Question

I want to check if any sequence of the elements of an array is repeating and be able to set the size of the sequence. For example:

var array = ["a", "b", "c", "d", "b", "c", "a"]

If you check for size = 1 (meaning if any single element is repeating) I should get true

If you check for size = 2 (meaning if any 2 elements are repeating ) I should get true (b,c sequence is repeating)

If you check for size = 3 I should get false

Thank you for your help. I am really stuck with this one

Answer 1

Another way of solving the task would be checking whether the hash (concatenated values) across sliding window of width N is seen more than once:

const src = ['a', 'b', 'c', 'd', 'b', 'c', 'a'],

      hasDupSeqOfSizeN = (arr, N, hashMap=[]) =>
        arr.some((_,i,__,hash=arr.slice(i,i+N).join('\ud8ff')) => 
          hashMap.includes(hash) || (hashMap.push(hash), false))
        
console.log(hasDupSeqOfSizeN(src,2))

.as-console-wrapper{min-height:100%;}

Answer 2

This might not be the most efficient answer, but it should get you what you're looking for

function checkSeq(arr, size) {
    for (var i = 0; i < arr.length; i++) {
      for (var j = i+1; j < arr.length; j++) {
        if (arr[i] === arr[j] && isValidSequence(arr, i, j, size)) {
          return true;
        }
      }
    }
    return false;
  }

function isValidSequence(arr, i, j, size) {
    for (var k = 1; k < size; k++) {
      if (j+k >= arr.size || arr[i+k] !== arr[j+k]) {
        return false;
      }
    }
    return true;
  }

I checked your 3 conditions and got the correct responses

checkSeq(array, 1) // true

checkSeq(array, 2) // true

checkSeq(array, 3) // false

Answer 3

Here is a solution that should work for array items that are not just characters:

const array = ["a", "b", "c", "d", "b", "c", "a", "a", "a", "b", "c"]

function checkSequence(sequence, size) {
    const matches = {}; // Stores counts of potential seqences, eg. { 'a,b': 1, 'b,c': 2 }

    for (let i = 0; i <= sequence.length - size; i++) {
        const current = sequence.slice(i, i + size); // get n items following each other starting at i
        // If match exists, increase count, else first match
        if (matches[current]) {
            ++matches[current];
        } else {
            matches[current] = 1;
        }
    }

    // Find first sequence that repeats and return true
    for (const seq in matches) {
        if (matches[seq] >= 2) {
            return true;
        }
    }

    return false;
}

console.log(checkSequence(array, 1));
console.log(checkSequence(array, 2));
console.log(checkSequence(array, 3));
console.log(checkSequence(array, 4));

matches is used to keep count of each processed sequence and is increased accordingly. The input array has been expanded to confirm that it works correctly.

The code can still be optimized by returning earlier, as soon as an existing match is found instead of looping through each of the matches at the end of the function.

Edit: Here is updated code that would check if the next match overlaps with the previous match. If there's an overlap, it does not consider it a match and continues with the search, else it will return true as soon as a match is found.

const array = ["a", "b", "c", "d", "e", "c", "d", "e", "c", "d"];

function checkSequence(sequence, size) {
  const matches = [];

  for (let i = 0; i <= sequence.length - size; i++) {
    // Assuming numbers or characters only
    const current = sequence.slice(i, i + size).join();

    // You'll need a different way to store/compare for other data types
    if (matches.find(match => match.value === current && i >= match.end)) {
      return true;
    } else {
      matches.push({ value: current, end: i + size });
    }
  }

  return false;
}

console.log(checkSequence(array, 1));
console.log(checkSequence(array, 2));
console.log(checkSequence(array, 3));
console.log(checkSequence(array, 4));
console.log(checkSequence(array, 5));