Hackerrank medium: Bear and Steady Gene (n^2 timeout solution - works but too slow)

Bear and Steady Gene.js

// https://www.hackerrank.com/challenges/bear-and-steady-gene/problem

function steadyGene(gene) {
  const geneArray = gene.split("");
  const geneDict = geneArray.reduce(
    // O(n) time
    (dict, char) => {
      return {
        ...dict,
        [char]: dict[char] + 1,
      };
    },
    { A: 0, T: 0, C: 0, G: 0 }
  );

  const steadyCountPerGene = gene.length / 4;

  const diffDict = {};

  for (const char in geneDict) {
    // O(n) time
    const charCount = geneDict[char];
    diffDict[char] = charCount - steadyCountPerGene;
  }

  const totalCountOfAllExceededChars = Object.values(diffDict).reduce(
    // O(n) time
    (total, charCount) => {
      return charCount > 0 ? total + charCount : total;
    },
    0
  );

  // start with sliding window of total number of exceeded counts => 5As + 1T = 6 characters minimum
  let subsequenceSize = totalCountOfAllExceededChars;
  let index = 0;
  let found = false;

  // this is O(n^2) time complexity
  // max n shifts in sliding window
  // max n different sliding window sizes
  while (!found) {
    const subsequence = geneArray.slice(index, subsequenceSize + index);

    if (subsequence.length !== subsequenceSize) {
      // this means the subsequence has just exceeded the tail end of the gene
      // increment subsequence size and start checking again from the beginning of the gene
      index = 0;
      subsequenceSize++;
      continue;
    }

    if (geneArray.length === subsequence.length) {
      return geneArray.length;
    }

    const subsequenceDict = subsequence.reduce(
      // O(n) time
      (dict, char) => {
        return {
          ...dict,
          [char]: dict[char] ? dict[char] + 1 : 1,
        };
      },
      { A: 0, T: 0, C: 0, G: 0 }
    );

    if (contains(subsequenceDict, diffDict)) {
      found = true;
    }

    index++;
  }

  return subsequenceSize;
}

function contains(main, sub) {
  for (const key in sub) {
    // O(1) time
    if (main[key] < sub[key]) {
      return false;
    }
  }
  return true;
}

// console.assert(steadyGene("AATT") === 2); // ACGT
// console.assert(steadyGene("AAAATTTT") === 4); // AAGGCCTT
// console.assert(steadyGene("CATTATCCTATC") === 4); // AAGGCCTT

// my macbook pro struggles to compute this
console.log(
  steadyGene(
    "AAAAAAAAAAAAATTTTTTTTTCTTTTTTTTGATTTTTATATATATATTTCCGTAAAAAAAAAAAAATTTTTTTTTCTTTTTTTTGATTTTTATATATATATTTCCGTAAAAAAAAAAAAATTTTTTTTTCTTTTTTTTGATTTTTATATATATATTTCCGTAAAAAAAAAAAAATTTTTTTTTCTTTTTTTTGATTTTTATATATATATTTCCGTAAAAAAAAAAAAATTTTTTTTTCTTTTTTTTGATTTTTATATATATATTTCCGTAAAAAAAAAAAAATTTTTTTTTCTTTTTTTTGATTTTTATATATATATTTCCGTAAAAAAAAAAAAATTTTTTTTTCTTTTTTTTGATTTTTATATATATATTTCCGTAAAAAAAAAAAAATTTTTTTTTCTTTTTTTTGATTTTTATATATATATTTCCGTAAAAAAAAAAAAATTTTTTTTTCTTTTTTTTGATTTTTATATATATATTTCCGTAAAAAAAAAAAAATTTTTTTTTCTTTTTTTTGATTTTTATATATATATTTCCGTAAAAAAAAAAAAATTTTTTTTTCTTTTTTTTGATTTTTATATATATATTTCCGTAAAAAAAAAAAAATTTTTTTTTCTTTTTTTTGATTTTTATATATATATTTCCGTAAAAAAAAAAAAATTTTTTTTTCTTTTTTTTGATTTTTATATATATATTTCCGTAAAAAAAAAAAAATTTTTTTTTCTTTTTTTTGATTTTTATATATATATTTCCGTAAAAAAAAAAAAATTTTTTTTTCTTTTTTTTGATTTTTATATATATATTTCCGTAAAAAAAAAAAAATTTTTTTTTCTTTTTTTTGATTTTTATATATATATTTCCGTAAAAAAAAAAAAATTTTTTTTTCTTTTTTTTGATTTTTATATATATATTTCCGTAAAAAAAAAAAAATTTTTTTTTCTTTTTTTTGATTTTTATATATATATTTCCGTAAAAAAAAAAAAATTTTTTTTTCTTTTTTTTGATTTTTATATATATATTTCCGTAAAAAAAAAAAAATTTTTTTTTCTTTTTTTTGATTTTTATATATATATTTCCGTAAAAAAAAAAAAATTTTTTTTTCTTTTTTTTGATTTTTATATATATATTTCCGTAAAAAAAAAAAAATTTTTTTTTCTTTTTTTTGATTTTTATATATATATTTCCGTAAAAAAAAAAAAATTTTTTTTTCTTTTTTTTGATTTTTATATATATATTTCCGTAAAAAAAAAAAAATTTTTTTTTCTTTTTTTTGATTTTTATATATATATTTCCGTAAAAAAAAAAAAATTTTTTTTTCTTTTTTTTGATTTTTATATATATATTTCCGTAAAAAAAAAAAAATTTTTTTTTCTTTTTTTTGATTTTTATATATATATTTCCGTAAAAAAAAAAAAATTTTTTTTTCTTTTTTTTGATTTTTATATATATATTTCCGTAAAAAAAAAAAAATTTTTTTTTCTTTTTTTTGATTTTTATATATATATTTCCGTAAAAAAAAAAAAATTTTTTTTTCTTTTTTTTGATTTTTATATATATATTTCCGTAAAAAAAAAAAAATTTTTTTTTCTTTTTTTTGATTTTTATATATATATTTCCGTAAAAAAAAAAAAATTTTTTTTTCTTTTTTTTGATTTTTATATATATATTTCCGTAAAAAAAAAAAAATTTTTTTTTCTTTTTTTTGATTTTTATATATATATTTCCGTAAAAAAAAAAAAATTTTTTTTTCTTTTTTTTGATTTTTATATATATATTTCCGTAAAAAAAAAAAAATTTTTTTTTCTTTTTTTTGATTTTTATATATATATTTCCGTAAAAAAAAAAAAATTTTTTTTTCTTTTTTTTGATTTTTATATATATATTTCCGTAAAAAAAAAAAAATTTTTTTTTCTTTTTTTTGATTTTTATATATATATTTCCGTAAAAAAAAAAAAATTTTTTTTTCTTTTTTTTGATTTTTATATATATATTTCCGTAAAAAAAAAAAAATTTTTTTTTCTTTTTTTTGATTTTTATATATATATTTCCGTAAAAAAAAAAAAATTTTTTTTTCTTTTTTTTGATTTTTATATATATATTTCCGTAAAAAAAAAAAAATTTTTTTTTCTTTTTTTTGATTTTTATATATATATTTCCGTAAAAAAAAAAAAATTTTTTTTTCTTTTTTTTGATTTTTATATATATATTTCCGTAAAAAAAAAAAAATTTTTTTTTCTTTTTTTTGATTTTTATATATATATTTCCGTAAAAAAAAAAAAATTTTTTTTTCTTTTTTTTGATTTTTATATATATATTTCCGTAAAAAAAAAAAAATTTTTTTTTCTTTTTTTTGATTTTTATATATATATTTCCGTAAAAAAAAAAAAATTTTTTTTTCTTTTTTTTGATTTTTATATATATATTTCCGTAAAAAAAAAAAAATTTTTTTTTCTTTTTTTTGATTTTTATATATATATTTCCGTAAAAAAAAAAAAATTTTTTTTTCTTTTTTTTGATTTTTATATATATATTTCCGTAAAAAAAAAAAAATTTTTTTTTCTTTTTTTTGATTTTTATATATATATTTCCGTAAAAAAAAAAAAATTTTTTTTTCTTTTTTTTGATTTTTATATATATATTTCCGTAAAAAAAAAAAAATTTTTTTTTCTTTTTTTTGATTTTTATATATATATTTCCGTAAAAAAAAAAAAATTTTTTTTTCTTTTTTTTGATTTTTATATATATATTTCCGTAAAAAAAAAAAAATTTTTTTTTCTTTTTTTTGATTTTTATATATATATTTCCGTAAAAAAAAAAAAATTTTTTTTTCTTTTTTTTGATTTTTATATATATATTTCCGTAAAAAAAAAAAAATTTTTTTTTCTTTTTTTTGATTTTTATATATATATTTCCGTAAAAAAAAAAAAATTTTTTTTTCTTTTTTTTGATTTTTATATATATATTTCCGTAAAAAAAAAAAAATTTTTTTTTCTTTTTTTTGATTTTTATATATATATTTCCGTAAAAAAAAAAAAATTTTTTTTTCTTTTTTTTGATTTTTATATATATATTTCCGTAAAAAAAAAAAAATTTTTTTTTCTTTTTTTTGATTTTTATATATATATTTCCGTAAAAAAAAAAAAATTTTTTTTTCTTTTTTTTGATTTTTATATATATATTTCCGTAAAAAAAAAAAAATTTTTTTTTCTTTTTTTTGATTTTTATATATATATTTCCGTAAAAAAAAAAAAATTTTTTTTTCTTTTTTTTGATTTTTATATATATATTTCCGTAAAAAAAAAAAAATTTTTTTTTCTTTTTTTTGATTTTTATATATATATTTCCGTAAAAAAAAAAAAATTTTTTTTTCTTTTTTTTGATTTTTATATATATATTTCCGTAAAAAAAAAAAAATTTTTTTTTCTTTTTTTTGATTTTTATATATATATTTCCGTAAAAAAAAAAAAATTTTTTTTTCTTTTTTTTGATTTTTATATATATATTTCCGTAAAAAAAAAAAAATTTTTTTTTCTTTTTTTTGATTTTTATATATATATTTCCGTAAAAAAAAAAAAATTTTTTTTTCTTTTTTTTGATTTTTATATATATATTTCCGTAAAAAAAAAAAAATTTTTTTTTCTTTTTTTTGATTTTTATATATATATTTCCGTAAAAAAAAAAAAATTTTTTTTTCTTTTTTTTGATTTTTATATATATATTTCCGTAAAAAAAAAAAAATTTTTTTTTCTTTTTTTTGATTTTTATATATATATTTCCGT"
  )
);

// === Below is ChatGPT's explanation of why this algorithm has a bad time complexity of O(n^2) ===
/**
 * Let's zoom in on the while (!found) loop and break it down step by step:

const subsequence = geneArray.slice(index, subsequenceSize + index);

This line creates a subsequence from the geneArray based on the current sliding window. The slice operation takes a portion of the array starting from the index and with a length of subsequenceSize.
Time complexity: O(n), where n is the length of the gene string. In the worst case, when the subsequence size is close to the length of the gene string, this operation takes O(n) time.
const subsequenceDict = subsequence.reduce(...)

This line creates a dictionary subsequenceDict that counts the occurrences of each character in the subsequence. The reduce operation iterates over each character in the subsequence and updates the dictionary accordingly.
Time complexity: O(n), where n is the length of the subsequence.
if (contains(subsequenceDict, diffDict)) { found = true; }

This line checks if the subsequence satisfies the conditions by calling the contains function, which compares the counts of characters in subsequenceDict with the corresponding counts in diffDict.
Time complexity: O(1), constant time operation.
index++;

This line increments the index to slide the window, moving to the next position in the geneArray.
Time complexity: O(1), constant time operation.
The key factor that determines the overall time complexity of the while (!found) loop is the sliding window size. The size of the sliding window starts at totalCountOfAllExceededChars and increases by 1 in each iteration. Therefore, the maximum number of iterations of the loop is roughly equal to the difference between the length of the gene string and totalCountOfAllExceededChars.

In the worst case scenario, when the sliding window size approaches the length of the gene string, the loop performs O(n) iterations. For each iteration, steps 1 and 2 both have time complexity of O(n). Hence, the overall time complexity of the while (!found) loop is O(n^2) since it performs O(n) iterations and has O(n) operations within each iteration.

It's important to note that this analysis assumes that the contains function has a constant time complexity, which is true in this case as it iterates over a fixed number of characters in the diffDict.
 */